S. Rajasekaran et S. Ramaswami, OPTIMAL MESH ALGORITHMS FOR THE VORONOI DIAGRAM OF LINE SEGMENTS AND MOTION PLANNING IN THE PLANE, Journal of parallel and distributed computing, 26(1), 1995, pp. 99-115
Citations number
33
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
The motion planning problem of an object with two degrees of freedom m
oving in the plane can be stated as follows: Given a set of polygonal
obstacles in the plane, and a two-dimensional mobile object B with two
degrees of freedom, determine if it is possible to move B from a star
t position to a final position while avoiding the obstacles. If so, pl
an a path for such a motion. Techniques from computational geometry ha
ve been used to develop exact algorithms for this fundamental case of
motion planning. In this paper we obtain optimal mesh implementations
of two different methods for planning motion in the plane. We do this
by first presenting optimal mesh algorithms for some geometric problem
s that, in addition to being important substeps in motion planning, ha
ve numerous independent applications in computational geometry. In par
ticular, we first show that the Voronoi diagram of a set of n noninter
secting (except possibly at endpoints) line segments in the plane can
be constructed in O(root n) time on a root n x root n mesh, which is o
ptimal for the mesh. Consequently, we obtain an optimal mesh implement
ation of the sequential motion planning algorithm described by O'Dulai
ny and Yap (J. Algorithms 6 (1985), 104-111); in other words, given a
disc B and a polygonal obstacle set of size n, we can plan a path (if
it exists) for the motion of B from a start position to a final positi
on in O(root n) time on a mesh of size n. We also show that the shorte
st path motion between a start position and a final position for a con
vex object B (of constant size) moving among convex polygonal obstacle
s of total size n can be found in O(n) time on an n x n mesh, which is
worst-case optimal. (C) 1995 Academic Press, Inc.