High-Clearance Motion Planning for a
Convex Polygon among Polygonal Obstacles
L. Paul Chew
Klara Kedem
TR 90-1133
June 1990
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*Work on this paper has been supported by ONR Contract N0001 4-86K-0281, by
DARPA under ONR Contract N0014-88-K-0591, MSl Grant U03-8300, and NSF Grant
DMC-86-1 7355. Work by second author was partly supported by the Pikkowski-
Valazzi Fund.
High-Clearance Motion Planning for a Convex Polygon among
Polygonal Obstacles
L. Paul Chew?1? & Kiara Kedem(1,2?
(1)Department of Computer Science
Cornell University
Ithaca, NY 14853
(2)Depaitment of Computer Science
Tel-Aviv University
Tel-Aviv 69978, Israel
ABSTRACT
We develop a high-clearance motion planning technique for a con-
vex polygonal object moving among polygonal obstacles in the plane. We
allow both rotation and translation (general motion). Ulven a k -sided
convex polygonal object P, a set of polygonal obstacles with n comers
and edges, and given initial and final positions for P, the time needed to
determine a high-clearance, obstacle-avoiding path for P is
0 (k4n ?(kn) log n), where ? is one of the almost-linear flinctions
related to Davenport-Schinzel sequences. This time bound compares
favorably with the time bound of 0 (kn ?(kn) log(kn)) achieved by
Kedem and Sharir for motion planning without high-clearance,
Key words; computational geometry, motion planning, edge Voronoi diagram, algorithm,
Davenport-Schinzel sequences.
Work on this paper has been supporeed by DARPA under 0NR contract NOC) 14-38-K-059 I. MSI grant UO3-83O0 and NSF
grant DMC-86- 17355. Work by second author was partly supported by the Pikkowski-Vaiazzi Fund.
-2-
1. Introduction
We develop an algorithm for high-clearance motion planning in the plane allowing
both translation and rotation (general motion). For a k-sided convex object moving
among polygonal obstacles with n corners and edges, the time needed to determine a
path is 0 (k4n ?3(l:n) log n), where X3 is one of the almost-linear functions related to
Davenport-Schirizel sequences.
The time bound for our high-clearance algorithm compares favorably with the time
bound of 0 (kn ?(&n) log(kn)) achieved by Kedem and Sharir [KS] for motion planning
without high-clearance. Their algorithin dictates that for much of the motion the object
remain in contact with the obstacles. In practice, this type of motion is undesirable:
small errors in the control of the motion can cause the object to crash into the obstacle, or
friction can cause the object to bind.
Our technique is based on the intuitively appealing idea that motion along Voronoi
boundaries provides maximum clearance. A number of authors have developed motion
planning techniques based on this idea; we briefly describe some of these results.
O'Dunlaing and Yap [OY] exploit the properties of the edge Voronoi diagram (also
called a generalized Voronoi diagram in the literature) to produce a motion planning
algoritbm for a disc. (An edge Voronoi diagram is a Voronoi diagram for line segments
as well as points; see Section 2.) Leven and Sharir [LS] have shown that a similar tech-
nique can be used to plan the translational motion of a convex polygonal object (call it
P) among convex polygonal obstacles. They use an edge Voronoi di?gram based on a
convex distance function where P itself is used to define the distance function (see also
[CD], [Fo]). Unfortunately, this technique allows only translational motion; rotation of
P changes the structure of the Voronoi diagram.
We develop a method for keeping track of the changes in the Voronoi diagram as
the orientation of P changes. If we plot the changing Voronoi diagram in (x ,y ,e) space
we get a collection of cells in 3-space. We show that this Voronoi cell-complex is not
-3-
large by using an analysis technique developed in [CK] to derive a bound on the number
of changes that can take place in a Voronoi diagram as the distance-defining convex
shape is rotated.
Using this Voronoi cell-complex, we construct a skeleton, a graph that contains all
the information necessary to do high-clearance motion planning. This skeleton includes
all the edges of the cell-complex plus some additional edges. We show that the number
of additional edges does not exceed a constant times the number of faces in the cell-
complex. Moreover, we show that there is a path for P in the plane (allowing both trans-
lation and rotation) if and only if there is a path on the skeleton, and that the path on the
skeleton has at least as much clearance as the path in the plane.
In outline, the skeleton is built using the following steps: To start, we choose an
arbitrary initial orientation 0 and compute the Voronoi diagram for our set of obstacles
using a distance function determined by the object P at angle 8. Since the Voronoi
diagram for a fixed 0 is not large, we can use a simple priority queue scheme to keep
track of changes in the Voronoi diagram as 0 changes. As changes in the Voronoi
diagram are computed, the skeleton can be built on the fly. Once the skeleton is com-
plete, it can be used to plan motion for any given initial and final positions of P
To plan motion using the skeleton, we first trim the skeleton by deleting any edges
where the clearance is too small (the definition of "too small" depends on the amount of
clearance the user desires). We then apply a simple method to get from the initial posi-
tion of P to the skeleton and from the skeleton to the final position of P. Th? poflion of
the path that is entirely on the skeleton can be found using depth-first-search. `
Remark. Note that a single skeleton, computed as outlined above, can be used to plan
high-clearance motion for any object that is similar to P. In other words, if you had a
large square robot and a small square robot, you could compute one skeleton to do
motion planning for both robots. Of course, for the large robot, more edges of the skele-
ton would have clearance considered "too small"
-4-
The paper is organized as follows. The edge Voronoi diagram (EVD) is discussed
in Section 2. In Section 3 we describe the Voronoi cell-complex and show how a path in
the plane corresponds to a path on the surface of the cell-complex. In Section 4 we
describe the skeleton of the cell-complex and show how a path on the surface of the cell-
complex corresponds to a path on the skeleton. Section 5 contains an outline of the
resulting algorithin and an analysis of its running time. Conclusions, some additional
observations, and some directions for flirther research appear in Section 6.
2. The edge Voronoi diagram
In this section we briefly describe the edge Voronoi diagram (EVD) and how it can
be used for tr&islational motion plannmg. In the literature, the EVD is often called a
generalized Voronoi diagram, but there are so many different possible generalizations of
the Voronoi diagram that it seems worthwhile to use a name that indicates which general-
ization is meant.
For an EVD, the initial data items (called sources) consist of points and line seg-
ments, while for a standard Voronoi diagram, the initial data consists only of points. For
the BVD, we distinguish two kinds of sources: (1) open line segments and (2) points
(including the endpoints of the line segments). We require that the open line segments
do not intersect. The Voronoi region for a given source is, as for t?e standard Voronoi
diagram, the portion of the plane that is closer to the given source than t6 any other
source. The standard F?D (the EVD using the standard Euclidean distance?ftiriction)
subdivides the plane into regions with boundaries consisting of line segments and seg-
ments of parabolas. An 0 (n log n) divide and conquer algorithin for building the EVD
has been developed by Yap [Ya]. Fortune's sweep4ine technique [Fo] can also be used
to build the BVDinO(n logn)time.
-5-
The EVD has the empty circle property: two sources share a Voronoi boundary iff
there is a circle through the two sources that does not contain any other sources (or por-
tions of sources).
The convex polygon as a distance function
We would like to clarify the meaning of this empty circle property for our motion
planning problem. Note that the meaning of circle depends on the distance function
being used. For instance, when the distance is defined by the L1 metric then a circle is a
square tipped at 450; when using the L2 metric (Euclidean distance), a circle is a stan-
dard circle; for a general convex distance function, a circle is a shape similar to and at
the same orientation as the distance-defining convex shape. For our motion planning
problem, a circle is a polygon geometrically similar to our movmg convex polygon P.
The edge Voronoi diagram, with a convex polygon P as a distance function, is
described in detail by Leven and Sharir [Ls]. They used it to generate high-clearance
transiational motion for a convex polygonal body P amidst polygonal obstacles in the
plane. We define (as in [LS]) the convex distance function defined by P, from a point p
to apoint q, by dp(p,q)=inf(?: q E p+?lP], and call it the P-distance fromp to q
(Note that this distance function does not have the symmetry property, and is therefore
not a metric). Intuitively, dp (p ,q) is how much one should expand (or contract) P,
when its center c is on p, so that the expanded P contains q.
The EVD defined by P -distance subdivides the plane into regions with boundaries
consisting of polygonal lines (no parabolas), see Figure la. Each polygonal boundary
line that connects two adjacent EVD vertices is a bisector equidistant (P -distance) from
two obstacles (sources). The EVD boundaries are one-dimensional when the sources and
P are in general position.
Sources are not in general position if a side of P is parallel to the line connecting
two obstacle corners. In this case, a bisector can include areas. In Figure lb the shaded
-6-
Figure la: A Voronoi diagram using a square as the distance function.
Figure ib: A Voronoi diagram where the obstacles are not in general position.
triangles are two-dimensional bisectors, and are actually the loci of all P `s centers such
that P touches the two obstacles (i.e., each point in the shaded triangle is equidistant
from the two obstacles). Since we allow P to rotate, each side of P can eventually
become parallel to each?palr of obstacle comers; thus, we must take these bisector-areas
into account in our Voronoi cell-complex.
We distinguish between two types of vertices that occur in the EVD: Voronoi ver-
tices that are intersections of three or more bisectors, and bisector vertices. Bisector ver-
tices are places where the polygonal bisector changes slope. Note that:
-7-
o+ A point p is on a bisector iff there is an empty circle (in the shape of P, the
distance-defining convex polygon) centered at p that touches two sources.
o+ A point p is a Voronoi vertex iff there is an empty circle centered at p that touches
3 or more sources.
o+ A point p is a bisector vertex iff there is an empty circle centered at p that touches
two sources, one of which is a point source that is touched by a corner of the empty
circle.
If the number of obstacles is n and the number of corners of P is k, then the EVD
can be built in 0 (An log An) time and 0 (An) space; this includes 0(n) space for the
Vor?noi vertices and 0 (An) space for the descriptions of the polygonal lines that are the
bisectors [LS].
Note: In order to obtain a bound based on the number of obstacles, Leven and Sharir
assume that the obstacles are convex, while in our work, we assume that the obstacles
consist of points and open line segments (this means that Voronoi boundaries are built in
the interiors of obstacles, but these regions are inaccessible anyway since they can be
reached only on a path with zero clearance).
3. The Voronoi Cell-Complex
In this section we describe how to extend the EVD, based on a convex polygon P at
a fixed orientation 0, to a Voronoi cell-complex, valid for every orientation 0 of P. We
also show that there is a path for P in the plane (allowing both translation and? r9tation)
iff there is a path on the surface of the cell complex. To do this, we impose an additional
condition: that the space that contains the obstacles is bounded. (This is no real loss of
generality since, given a set of obstacles, we can always build a box around the obstacles
that is large enough so that no reasonable paths are disturbed.)
-8-
Let us denote the polygon P at orientation 0 by P 0 The P 0-distance between two
points p and q is defined (as above) by
d0(p,q)=inf(?t:q Ep +pLPQ).
We use EVD0 to denote the edge Voronoi diagram created using the P0-distance.
The following theorem provides a bound on the number of topological changes that
can occur in the EVD as P, the distance-defining convex shape, is rotated.
Theorem 1 [CK]: Given a convex polygon P with k sides, and given a set S of 71
sources (line segments and points), the EVD for S using a distance function derived from
P at orientation 0 changes 0 (k4n X3(kn)) times as 0 goes from 0 to 2?.
Proof: This result is an immediate consequence of the bound proved in [CK] on the
number of changes in the dual of the EVD. The bound has been improved slightly by
applying a technique from [OSS] to convert X4 in [CK] to ?? here. ?
If we look at EVD0 in (x ,y ,0) space, as 0 changes, the boundaries around each
source sweep out a sufface (a sleeve) that surrounds the source. Calling the 0 direction
`vertical", the sources themselves sweep out either a vertical line or a portion of a verti-
cal plane, for a point source or an open line-segment source, respectively.
For the most part, the sleeve around a source changes in a smooth fashion: vertices
(both Voronoi vertices and bisector vertices) move continuously as 0 changes; orienta-
tions of the boundary segments also change gradually as 0 changes. An abrupt change
can occur only in the sleeve around a point source; this happens wheneveY we reach a
value of 0 for which there exists a bisector area (i.e., the sources and P are not in general
position). Thus, the sleeve around a point source can include a flat horizontal area (tak-
ing 0 as vertical) called a shelf
To help the reader visualize the Voronoi cell-complex, we provide some examples.
In Figure 2 we show a topological change in the EVD that occurs at orientation 0.
Assume A, B, C and D are the obstacles (for the sake of simplicity we assume the
-9
EvDo
B			B
bc			A
D			D
D
Figure 2: Changes in the EVD.
obstacles are points). At 0 the four EVD0 edges ab, bc, ad and cd meet at vertex X.
The edge ac in EVD ?? disappears as 0 increases while edge bd emerges in EVD ??+??.
Figure 3 shows the changes of EVD0 when there is a shelf. (The Voronoi diagram is
represented by solid lines; the dashed lines represent P.) At orientation 0, one side of P
is parallel to the line through a and b
?e--He
a			b
EVDe
a			b
`wDo+?
a
Figure 3: A bisector area that causes a shelf.
b
At this point, we want to show how a path for P in the plane (with rotation)
corresponds to a path for a point on the surface of the cell-complex. First, note that there
is a simple correspondence between a motion (translation and/or rotation) of P in the
- 10-
plane and motion of a single point (corresponding to the center of P) in (x ,y ,?) space.
Lemma 1: For every legal (noncolliding) motion of P in the plane there is a motion of c,
the center of P, in (x ,y ,O) space that is at least at distance 1 from each obstacle. (Recall
that distance is defined in terms of P.)
Proof: A simple consequence of the definitions. ?
Next we want to show how a path for a point in (x ,y ,?) space is projected away
from the sources to a path on the surface of the cell-complex. At an intuitive level, we
think of the obstacles as light-sources; the original path corresponds to a wfre in 3-space
and the path on the surface of the cell-complex corresponds to the wfre's shadow. If
p = (x ,y ,?) is a point on the original path then its shadow on the surface of the cell-
complex has the same value of e; call this shadow s (p). Given EVD e and a point p in
some region R of EVD0, the corresponding shadow s (p) can be found using the follow-
ing steps (a similar technique was used by Leven and Sharir [Ls]).
1. Let r be the source in region R and let q be the point of i that is closest to p. (Of
course, if r is a point-source then q = r.) Note that "closest" here means "closest
using the P0 distance". In other words, we take a small copy of P0, place its center
at p and expand it until it touches r; q is the point at which it touches r.
2. Draw a ray from q through p. The shadow s (p) is defined to be the point at which
this ray intersects the boundary of R (see Figure 4).
The shadow projection technique outlined above produces a continuous path on the
surface of the cell-complex except for shelves (bisector areas). For a shelf the projected
path is likely to end on one side of the shelf and start up agam on another sid?. For-
tunately, there is a simple way to connect the two loose ends, again using the intuitive
idea of shadow projection: we add the shadow cast on the surface of the shelf (Figure
5a). If the original path penetrates a shelf then we get two shadows, one for each of the
two sources for which the shelf is a bisector (Figure 5b).
- 11 -
Figure 4: The shadow.
7
/tI
?p2
(a)			(b)
Figure 5: Shadows on a shelf,
The one remaining problem is to get from the initial (final) position of ?: to the sur-
face of the cell-complex Oiven p, the initial (final) position of P, where p is not neces-
salily on the surface of the cell-complex, we get to the surface by following the -to-
surface portion of the ray from q (the closest point of the source) through p to the sur-
face of the cell-complex.
Lemma 2: If there is a noncolliding a -to-b path for P among obstacles in a bounded
space then there exists a noncolliding a -to-b path for P which, except for its starting and
7,
- 12 -
ending segments, is entfrely on the surface of the cell-complex. Furthermore, the new
path has at least as much clearance as the original path.
Proof; Given a noncolliding a -to-b path for P we use the shadow-projection technique
described above to construct a new path with the necessary properties. If we ignore
shelves then we claim the projected path is continuous. This follows from the fact that a
Voronoi region for a convex distance function is star-shaped with respect to its source
(see [LS] or [CD]) and from the assumption that the original path is a noncolliding path
and thus cannot penetrate a source. The fact that the obstacle space is bounded, assures
us that each point of the original path is projected to a point on the surface of the cell-
complex. Shelves and the beginning and ending of the path are handled by introducing
new segments as described above, producing a continuous path from a to b.
To see that the new path has just as much clearance as the old path, note that each
point on the new path is derived from a point on the original path by moving away from
the closest source. This will increase clearance as long as we don't get too close to some
other source; this might in principle occur if, for instance, one of the added segments
intersects the Voronoi region for a different source. For the segments we add, this prob-
lem cannot occur since the Voronoi regions are star-shaped with respect to thefr sources.
This holds even for the segments added within shelves, since a shelf, as part of a bisector
between two sources, can be considered as belonging to the Voronoi region of either of
these two sources without affecting the star-shapedness of Voronoi regions. EJ
4. The Skeleton
Our next step is to construct a graph, called the skeleton of the Voronoi cell-
complex, that contains all the information necessary for high-clearance motion planning.
The skeleton includes all the edges and vertices of the Voronoi cell-complex plus a mod-
est number of additional edges and vertices. Our goal is to show that for any path on the
- 13
surface of the cell-complex there is a path on the skeleton that has just as much clear-
ance. Recall that the cell-complex is generated by EVD0 ? e changes. Thus, the edges
of the cell-complex are swept out by the vertices of EVD0, both bisector vertices and
Voronoi vertices. The initial skeleton consists entirely of these edges.
We start the process of creating additional skeleton edges by dividing the surface of
the Voronoi cell-complex into faces. Intuitively, a face is a surface that is generated by
a single edge of EVD e. A face begins or ends when its generating edge begins or ends.
Note that an edge ceases to exist when its length goes to zero or when its endpoint
changes. See Figure 6 for examples of how faces can begin and end. We make these
faces explicit in the skeleton by adding the top and bottom boundaries of faces to the
skeleton; thus, for each endpoint change in EVD0, we add one edge to the skeleton.
These extra edges leave us with the entire surface of the Voronoi cell-complex divided
into regions that are either faces or shelves. The boundaries of a face that are generated
by either a Voronoi vertex or a bisector vertex are roughly vertical (again taking e a
"up") and are referred to as the vertical sides of a face to distinguish these sides from the
horizontal edges due to shelves and endpoint changes.
Figure 6: Face chai?ges.
One useful property of the faces is that within a given face, locations of high and
low clearance are nicely behaved. Note that each edge of EVD0 has maximum clearance
-14-
at one end and minimum clearance at the other. This observation leads to the following
lemma.
Lernina 3: Each face of the Voronoi cell-complex has maximal clearance along one vert-
ical side and minimal clearance along the other. The maximal and minimal clearance
can switch sides at most once for a given face.
Proof; Consequence of the convexity of P. Maximal and minimal clearance cannot
switch at all unless the face is generated by a Voronoi boundary between the Voronoi
region of a point source and the Voronoi region of a line source. Such switching occurs
when the side of P that is in contact with the point source is parallel to the line source. [Zi
Since we want high-clearance paths, our favorite location on a given face should be
the edge with maximal clearance. Since, according to the previous lemma, this edge may
switch sides from one vertical side of the face to the other, we need a way to get from
one vertical edge to the other. In other words, we need to add one edge to the skeleton
for each face that switches its max- and min-sides. For each such face we add a new hor-
izontal edge at the value of 0 where the switch occurs.
Figure 7; Path-to-max-side projection.
Consider what happens to a path on the surface of the cell-complex; in particular,
what happens to a portion of a path that crosses a single face (see Figure 7). Intuitively,
15
we want to push the path away from the min-side of the face onto the max-side of the
face. This seems to work fine except where the path first enters the face; this entry point
gets "stretched" into a horizontal line across the face. We can't possibly include the
infinite set of all such horizontal edges in our skeleton, so we need some smaller set of
edges that can be used to travel across a face.
This problem is resolved by observing that when a path first enters the min-side of a
face, we can move anywhere we want along the min-side as long as we don't decrease
clearance. In other words, we can move from our entry point to a local maximum of the
mm-side. These local maxima are where we add new horizontal edges called bridges.
Thus, for each face of the cell-complex and for each local maximum along that face's
min-side, we add to the skeleton a bridge that goes across the face at the local maximum.
To see how this works, consider again a portion of a path across a face (see Figure 8). If
the path enters the min-side of the face, we extend the path by moving along the min-side
in the direction of increasing clearance until we hit a local maximum (or we hit the end
of the face), then we cross the face along the bridge to the max-side of the face, and
proceed along this side. The result is a path that travels entirely along the two sides of
the face except for some horizontal portions due to either a bridge or a switch of max-
and min-sides.
1			?V\ ?
Figure 8: Paths through local maxuna.
- 16
Our strategy of pushing the path toward the max-side will work as long as we do not
have to add too many of these bridges. The following lemma shows that oniy a few
bridges are needed per face.
Lemma 4: The clearance, computed as a function of distance along the vertical side of a
face, has most three local maxima.
Proof: The side of a face corresponds to either a Voronoi vertex or a bisector vertex. We
outline the proof for the Voronoi vertex case; the bisector vertex case is similar. A Voro-
noi vertex corresponds to the center of a scaled version of P that touches three obstacles.
Let ?(0) represent the size of P as P i? otdtt:d while maintaining contact with the same
three obstacles. If the obstacles are points then some straightforward trigonometry shows
that ?O#A sin(O+%) where A and O0 are constants. This has at most one max in a range
of size ?. If one obstacle is a line segment and the other two are points then the formula
for ?(0) is more difficult. For fixed-size P, it can be shown that if two sides remain in
contact with point obstacles then each comer of P must trace out a limacon
(r=A +B sinO). This information can be used to show that if the contacted obstacles are
two points and a line, there is at most one maximum and at most two minima for WO).
The remaining contact types are duals of these first two cases (i.e., take P as fixed and
consider rotating and scaling the set of obstacles). For these remaining cases the formulas
for W?) correspond to the recipricols of the earlier formulas. Looking at all these types
of contacts we see there are at most two local maxima, three if we include maxima at
endpoints. E3
We also need to be' able to handle paths on a shelf. Fortunately, shelves are easier
than faces; all we need to include for a shelf is the set of edges that describe its boundary.
Observe that a shelf is built of an infinite set of parallel lines where each such line is a
line of constant clearance (see Figure 9a). Clearance changes monotonically as we move
in the dfrection perpendicular to these lines. For any path that crosses a shelf, we travel
along the boundary from the entry point to the exit point, starting in the direction of
- 17.
increasing clearance (Figure 9b).
e
N
0
f
0
Figure 9a: Lines of constant clearance.
Lv\c
Cj )
Figure 9b: Path projected to the boundary of a shelf.
In summary, the skeleton is constructed by including the following edges for each
face of the cell-complex.
1.			The edges defining the boundaries of the face.			`a
2. If the min-side and the max-side of the face switch sides then we add a horizontal
edge across the face where this switch occurs. (At most one of these per face.)
3. At most four bridges per face. A bridge is a horizontal edge across the face for each
local maxima along along the min-side of the face. By Lemma 4 there are at most 2
- 18 -
such maxima per side (not counting possible endpoint maxima where we already
have edges connecting the sides) and part of each side might be a min-side.
In addition, the skeleton includes the boundaries of all shelves.
Now that the skeleton has been defined, we can show how it can be used for high-
clearance paths.
Lemina 5: If there is an a -to-b path on the surface of the cell-complex then there exists
an a -to-b path which, except for starting and ending segments, is entirely on the edges of
the skeleton. Furthermore, the new path has at least as much clearance as the original
path.
Proof: We use the projection technique described in the preceding paragraphs. The
bridges allow any path that crosses a face to be projected toward the max-side of the
face, increasing clearance. Note that the point at which a path enters a face and the point
at which a path exits a face are unchanged by this projection process; thus, the individual
projected paths for the faces can be pasted together to make a continuous path. Any path
that crosses a shelf can use the boundary instead, leaving entry and exit points
unchanged.
Starting and ending segments are also handled using the projection technique. If we
start on a face, we simply add a horizontal segment from the starting point to the max-
side of the face. If we start on a shelf, we add a horizontal edge perpendicular to the
lines of constant clearance that make up the shelf, and in the direction of increasing
clearance. Once we reach the boundary of the shelf, we can follow the boundary to the
point where the original path exits the shelf. Ending segments are handled just?il?e start-
ing segments.
An examination of these path-changing techniques shows that each technique
increases clearance. Thus, the new path has at least as much clearance as the old path. [Z
- 19 -
This lemma and the lemma at the end of the preceding section lead to the following
theorem.
Theorem 2: If there is a noncolliding a -to-b path for P among obstacles in a bounded
space then there exists a noncolliding a -to-b path for the center of P which, except for
two starting segments and two ending segments, is entirely on the edges of the skeleton.
Furthermore, the new path has at least as much clearance as the original path.
Proof: Follows directly from the two lemmas. EZ
5. Algorithmic details
The above theorem can be used to develop an algorithin for high-clearance motion
planning. We assume P is a convex polygon for which we wish to plan a high-clearance
path among polygonal obstacles. The algorithin consists of the steps outlined below.
1. Build the cell complex for P and the obstacles. This requires a number of substeps:
First, we build the EVD (edge Voronoi diagram) of the obstacles for some arbitrary
initial orientation of P. Each bisector of the EVD is placed in a priority queue with
priority equal to the angle at which it will disappear due to interactions with its
immediate neighbors. The strncture of the EVD is topologically unchanging except
at orientations (events) where a bisector disappears. The cell-complex is built as
each disappearance event is processed in turn. Each such event causes updates to
the priority queue: (1) a bisector disappears, (2) a new bisector appears, and (3)
neighbors of a new bisector must have their priorities updated since this new bisec-
tor can change the angle at which its neighbors disappear. a
2. Build the skeleton. We add the necessary edges to the edges of the cell-complex.
In practice, the skeleton can be built on the fly during step one, and building the
cell-complex is unnecessary.
-20-
3. Mark the edges of the skeleton where the clearance is "too small". This is done by
calculating the minimum clearance for each edge; then we mark edges that have
clearance of less than some number of units chosen by the user. (Recall that dis-
tances are measured using the P distance function; thus, a clearance of one unit
corresponds to P just touching an obstacle.) These edges are not used for determm-
ing a path, although portions of such edges might be used at the start or the end of a
path.
4. Compute the path. For the starting and ending positions, we compute segments that
get us first to the surface of the cell-complex and then to the skeleton. Once on the
skeleton, we can use any of a number of techniques (for instance, depth-first-search)
to find the rest of the path.
The running time of the above algorithm is dominated by the time it takes to handle
the cell-complex. Since the cell-complex is built using a priority queue, the time bound
is the size of the cell-complex multiplied by the time it takes for a queue operation. The
cell-complex is of size 0 (k4n X3(kn)) by Theorem 1. The priority queue contams at
most 0(n) items at any one orientation (there are 0 (n) bisectors in a Voronoi diagram
for n sources); thus, using any of a number of standard implementations, each queue
operation takes time 0 (log n). It follows that the cell-complex can be built in time
O(k4n ?(kn)logn).
The remainder of the algorithm takes time proportional to the cell-complex size or
o (k4n ?3(kn)). For step 2 of the algorithm, we have to analyze each face of the cell-
complex and add at mo?t a constant number of edges per face. In step 3, we check each
edge of the skeleton, taking time proportional to the size of the cell-complex. For step 4,
we have to do a search on the skeleton, a graph of size 0 (k4n ?(kn)).
The total running time is thus 0 (k4n X3(kn) log t?) where ic is the number of ver-
tices of P and n is the number of vertices and edges among the obstacles.
- 21
6. Conclusions and Further Research
We have developed an algorithm for planning a high-clearance motion for a convex
polygonal object in the plane moving among polygonal obstacles. If the moving convex
object has k vertices and if the obstacles contain a total of n vertices then the time to
plan the motion is 0 (k4n X3(kn)log n). To prove this result we used a bound developed
in [CK] on the number of changes that can occur m an edge Voronoi diagram as its
distance-defining convex shape is rotated.
High-clearance motion planning can be done somewhat faster for the special case in
which the obstacle set contains only isolated points. For this situation, results in [CK]
imply that the cell-complex is of size 0 (k2n X3(kn)). Thus, using the techniques
developed above, the time for high-clearance motion planning is 0 (k2n X3(kn)log n).
The motions produced by our motion planning algorithm deserve some comment.
In (x,y,O) space, motion along a horizontal skeleton edge (along a bridge, for instance) is
simply translation, but motion along a vertical skeleton edge is more complex, consisting
of simultaneous translation and rotation. This is because the vertical skeleton edges are
not, for the most part, exactly vertical; these edges are generated by Voronoi vertices
which translate somewhat as P is rotated. In practice, in order to communicate the
appropriate steps to a real robot, it may be necessary to describe the path by using a set of
discrete points along the true path, with the robot interpolating the path between the
points. There is some error inherent in this method, but since our paths are high-
clearance paths, collisions should rarely occur. This problem of discretizing complex
motions appears in all motion planning algorithms that allow both translatio? ai?d rota-
tion. AIgorithms that do not produce high-clearance paths are likely to suffer collisions,
since the motions produced are usually pefformed while in contact with one or more obs-
tacles.
The reader should note that the clearance discussed in this paper does not exactly
correspond to the usual intuitive notion of clearance. Our dearance is measured using
- 22 -
the convex distance function based on P,the object to be moved. For instance if P is a
rectangle (see Figure 10) and we ask for unit clearance around the edges of P then the
clearance at the sides looks like half the width of P and the clearance at the top and bot-
tom looks like half the height ofP
7
\ /
7
`i
Figure 10; Clearance in a rectangle's distance function.
Maximal clearance paths can be found by building a particular spanning tree of the
skeleton. The most straightforward way to do this is to sort the edges of the skeleton
based on their clearance, highest clearance first. We then build a tree by adding edges
one at a time, skipping any edges that create a loop in our prospective tree. A path on
this tree has the highest possible clearance. Note however, that, as mentioned in the
preceding paragraph, the clearance of the resulting maximal dearance path does not
correspond to the usual intuitive notion of clearance.
We suspect that too many factors of k appear in our time bound for motion plan-
ning. It seems likely ?at the correct time bound is 0 (kn X3(kn) log n).
References
[CD] L.P. Chew and R.L. Drysdale, Voronoi diagrams based on convex distance
functions, Proc. ACM Symposium on Computational Geomeny, 1985, pp. 235-
244.
- 23 -
[CK] L.P. Chew and K. Kedem, Placing the largest similar copy of a convex polygon
among polygonal obstacles, Proc. ACM Sympositim on Computational
Geometry, l989,pp. 167-174.
[Fo] 5. Fornine, A sweepline algorithin for Voronoi diagrams, Algorithmica, 2
(1987), pp. 153-174.
[055] L.j. Guibas, M. Sharir and 8. Sifrony, On the general motion planning problem
with two degrees of freedom, Discrete and Computational Geometry, (4)1989.
[KS] K. Kedem and M. Sharir, An efficient motion planning algorithm for a convex
polygonal object in 2-dimensional space, Discrete and Computational
Geometry, (5)1990.
[LS] D. Leven and M. Sharir, Planning a purely translational motion for a convex
polygonal object in two dimensional space using Generalized Voronoi
diagrams, Discrete and Computational Geometry, 2 (1987), pp. 9-31.
[OY] C. O'Dunlaing and C. Yap, ?? Voronoi diagram method for motion planning:
the case of a disc, J. Algorithms 6 (1985), pp. 104-111.
[Ya] C.K. Yap, An 0 (n logn) aIgorithm for the Voronoi diagram of a set of simple
curve segments, Discrete and Computational Geometry, 2 (1987), pp. 365-393.