Models and motion planning.
We study the complexity of the motion planning problem for a bounded-reach robot in the situation where the n obstacles in its workspace satisfy two of the realistic models proposed in the literature, namely unclutteredness and small simple-cover complexity. We show that the maximum complexity of the free space of a robot with f degrees of freedom in the plane is  (nf/2 + n) for uncluttered environments as well as environments with small simple-cover complexity. The maximum complexity of the free space of a robot moving in a three-dimensional uncluttered environment is (n2f/3 n). All these bounds fit nicely between the (n) bound for the maximum free-space complexity for low-density environments and the (nf) bound for unrestricted environments. Surprisingly--because contrary to the situation in the plane---the maximum free-space complexity is (nf) for a three-dimensional environment with small simple-cover complexity.
Introduction
It is well known that the maximum complexity of the free space of a robot with f degrees
of freedom moving in a scene consisting of n disjoint obstacles of constant complexity can
be # n f ). Consequently, exact motion-planning algorithms often have a worst-case running
time of at least the same order of magnitude. This is probably one of the reasons that most of
the exact algorithms were never implemented. One exception is Ba-non's implementation [3]
of the O(n 5 ) algorithm of Schwartz and Sharir [14] for a ladder moving in a two-dimensional
workspace, which performs surprisingly well, and much better than the worst-case theoretical
analysis predicts. The reason is that the running time of the algorithm is sensitive to the
actual complexity of the free space, and this is in practice far less than the #(n f ) worst-case
bound.
These observations inspired research [1, 2, 4, 7-11, 13, 15, 16, 19-21] where geometric problems
are studied under certain (hopefully realistic) assumptions on the input-in the case
of motion planning: the environment in which the robot is moving. The goal of this line of
research is to be able to predict better the practical performance of algorithms. For instance,
van der Stappen et al. [16] studied the free-space complexity for a bounded-reach robot moving
in environments consisting of fat obstacles. robot has bounded reach if it is not too large
compared to the obstacles in its workspace; an obstacle is fat if it has no long and skinny
# Institute of Information and Computing Sciences, Utrecht University, P.O.Box 80089, 3508
the Netherlands. Email: {markdb,markov,frankst,jules}@cs.uu.nl.
Department of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva
84105, Israel. Email: matya@cs.bgu.ac.il. Supported by the Israel Science Foundation founded by the Israel
Academy of Sciences and Humanities.
parts.) They showed that in this restricted type of environments the worst-case free-space
complexity is only #(n). Van der Stappen [17, 18] also proved that in such environments
naive and slightly adapted versions of Schwartz and Sharir's ladder algorithm run in O(n 2 )
and O(n log n) time, respectively, which is more in line with the experimental results of Ba-non.
der Stappen and Overmars [19] used the linear free-space complexity result to obtain
an e#cient general approach to robot motion planning amidst fat obstacles. These results
were extended to the more general setting of low-density environments by van der Stappen et
al. [20].
De Berg et al. [5] brought together various of the realistic input models that were proposed
in the literature, namely fatness, low density, unclutteredness, and small simple-cover
complexity-see Section 2 for formal definitions of these models. They showed that these
models form a strict hierarchy in the sense that fatness implies low density, which in turn
implies unclutteredness, which implies small simple-cover complexity, and that no other implications
exist between the models. A natural question that arises is whether the results of
van der Stappen et al. [20] remain valid when, instead of a low-density scene, we assume a
more general setting, like an uncluttered scene or a scene with small simple-cover complexity.
In other words, does the complexity of the free space of a bounded-reach robot with f degrees
of freedom moving in an uncluttered scene (alternatively, in a scene with small simple-cover
complexity) remain O(n)?
The main result of this paper is a negative answer to this question. We prove that
the maximum complexity of the free space of a bounded-reach robot moving in either an
uncluttered scene or a scene with small simple-cover complexity is #(n f/2 n) when the
workspace is two-dimensional. These bounds fit nicely between the #(n) bound for low-density
scenes and the #(n f ) bound for general scenes. For three-dimensional uncluttered
scenes the bound becomes #(n 2f/3 n). Contrary to the planar case, small simple-cover
complexity does not result in a reduced maximum free-space complexity for three-dimensional
workspaces: the maximum complexity is #(n f ).
Our upper-bound proofs use the concept of guarding sets [6]. A guarding set for a collection
of objects-in our case the obstacles in the robot's workspace-is, informally speaking, a set
of points (sometimes referred to as guards) that approximates the spatial distribution of these
objects. Guarding sets allow us to define a simplifying generalization [6] of unclutteredness
that implies small simple-cover complexity in 3D and is even equivalent to it in the plane.
Section 2 recalls the input models that play a role in this paper and briefly reviews the
relations between these models and the concept of guarding sets. Section 3 establishes an
upper bound on the number of large objects intersecting a hypercube given the number of
guards in its vicinity. In Sections 4 and 5 we use the relations and the bound to obtain tight
bounds on the maximum complexity of the free space for motion planning in uncluttered environments
and environments with small simple-cover complexity in 2D and 3D, respectively.
Section 6 concludes the paper.
Before we briefly describe the input models that play a role in this paper we list a few
important assumptions and definitions. The dimension of the (work)space is denoted as
d. We shall be dealing a lot with squares, cubes, rectangles, and so on. These are always
assumed to be axis-aligned. All geometric objects we consider are d-dimensional and open; in
particular, if we talk about a point lying in a square or cube, we mean that the point lies in
the interior of the square or cube. Furthermore, all objects we consider are assumed to have
constant complexity. More precisely, each object is a compact connected set in R d , bounded
by a constant number of algebraic surface patches of constant maximum degree.
The size of a square (more generally, of a hypercube) is defined to be its edge length, and
the size of an object is the size of a smallest enclosing hypercube for the object.
An L-shape is the geometric di#erence of a hypercube # with a hypercube # of less
than half its size and sharing a vertex with it. An L-shape can be covered by 2 d
hypercubes
contained in it: for each vertex v of # not shared with # , take the hypercube of maximal size
with v as a vertex and contained in # .
Although this paper concentrates on motion planning in uncluttered environments and
environments with small simple-cover complexity, we also briefly describe the model of low
density for the sake of reference. It is the weakest model for which the free space of a bounded-
reach robot is known to have linear complexity [20]. We leave fatness [5, 18, 19] out of our
discussion as it imposes stronger constraints on the environment while leading to the same
bound as low density.
The model of low density was introduced by van der Stappen et al. [20] and refined by
Schwarzkopf and Vleugels [15]. It forbids any ball B to be intersected by many objects whose
minimal-enclosing-ball radius is at least as large as the radius of B. In the definition, # meb (P)
denotes the radius of the minimal enclosing ball of an object P.
Definition 2.1 Let O be a set of objects in R d . We say that O has #-low-density if for
any ball B, the number of objects intersect B is at
most #.
We say that a scene has low density if it has #-low-density for a small constant #.
Unclutteredness was introduced by de Berg [4]. The model is defined as follows.
Definition 2.2 Let O be a set of objects in R d . We say that O is #-cluttered if any hypercube
whose interior does not contain a vertex of one of the bounding boxes of the objects in O is
intersected by at most # objects in O.
We call a scene uncluttered if it is #-cluttered for a small constant #.
The following definition of simple-cover complexity is a slight adaptation of the original
definition by Mitchell et al. [12], as proposed by de Berg et al. [5]. Given a scene O, we call
a ball #-simple if it intersects at most # objects in O.
Definition 2.3 Let O be a set of objects in R d , and let # > 0 be a parameter. A #-simple
cover for O is a collection of #-simple balls whose union covers the bounding box of O. We say
that O has (s, #)-simple-cover complexity if there is a #-simple cover for O of cardinality sn.
We will say that a scene has small simple-cover complexity if there are small constants s and
# such that it has (s, #)-simple-cover complexity.
Guarding sets [6] against hypercubes 1 provide a generalization of unclutteredness that
turns out useful in our proofs. A guarding set for a collection of objects is, loosely speaking,
a set of points that approximates the distribution of the objects. More precisely, guarding
sets are defined as follows.
1 In the paper by De Berg et al. [6] guarding sets are defined against an arbitrary family of ranges. It is
su#cient for our purposes to concentrate on hypercubic ranges.
Definition 2.4 Let O be a set of objects in R d , and let # be a positive integer. A set G of
points is called a #-guarding set for O (against hypercubes) if any hypercube not containing
a point from G intersects at most # objects from O.
We will often call the points in G guards.
We are particularly interested in scenes that admit a small #-guarding set for some small
constant #, that is, a guarding set of size linear in the number of objects in O. Scenes
that admit a linear-size guarding set fit nicely in the existing model hierarchy: a low-density
scene is also an uncluttered scene, which, is a scene that admits a linear-size guarding set,
which is a scene with small simple-cover complexity [5, 6]. In the plane admitting a linear-size
guarding set is even equivalent to having small simple-cover complexity, but this is not the
case in higher dimensions. A consequence of these hierarchical relations is that upper bounds
for scenes with linear-size guarding sets immediately transfer to planar and 3D uncluttered
scenes as well as to planar scenes with small simple-cover complexity. This conclusion will
come to our help in Sections 4 and 5.
3 Guards and vicinities
Guards provide information on the distribution of the objects in an environment. Let us
assume we are given a #-guarding set for a collection of objects. A hypercube without any
guards is, by definition, intersected by at most # objects. Moreover, a hypercube with exactly
guards in its interior is intersected by O(#g) objects [6]. Theorem 3.4 below states another,
more surprising, relation between the distribution of the objects and the distribution of the
guards. Again we look at hypercubes, but this time we only look at objects that are at least
as large as the hypercube, and not only consider the guards inside the hypercube but also the
ones in its vicinity.
We define the vicinity of a hypercube # to be the hypercube obtained by scaling # with a
factor of 5/3 with respect to its center. Thus, if we partition the vicinity of # into 5 d equal-sized
subhypercubes, then # consists of the 3 d middle subhypercubes. The planar case is
illustrated in Figure 1.
vicinity of #

Figure

1: A square # and its vicinity.
We will show that the number of objects intersecting a hypercube # in R d and at least as
large as # cannot be more than (roughly) O(g 1-1/d ), where g is the number of guards in the
vicinity of #.
We first reduce the problem to a simpler problem on so-called 3-blocks. Define a 3-block
to be the hyperrectangle obtained by scaling an axis-parallel hypercube by a factor of 1/3
along one of the coordinate axes. We say that an object crosses a given hyperrectangle if
there exists a curve inside the intersection of the hyperrectangle and the object that connects
the two largest (and opposite) faces of the hyperrectangle. First we prove that if a hypercube
is intersected by many larger objects, then there must be a 3-block in its vicinity that is
crossed by many objects.
Lemma 3.1 Let # be a hypercube intersected by a collection O of m objects that are at
least as large as #. Then there is a 3-block contained in the vicinity of # that is crossed by
at least m/(2d3 d ) objects.
Proof: Partition # into 3 d equal-sized subhypercubes. One of the subhypercubes, say # ,
intersects at least m/3 d objects. Denote the set of objects intersecting # by O # . Let # be
the hypercube obtained by scaling # with a factor three with respect to its center. Consider
the 2d 3-blocks that are contained in # and have one of the 2d sides of # as a face-see

Figure

2 for an illustration of the planar case. Note that # and, hence, all 2d 3-blocks, are
contained in the vicinity of #. We shall argue that one of the 3-blocks is crossed by at least
the four 3-blocks

Figure

2: Illustration of the planar case in the proof of Lemma 3.1.
The hypercube # has the same size as the original hypercube #. Hence, each object in
O is at least as large as # . This implies that the objects cannot be fully contained in # .
Thus, each object in O # has a point inside # and a point outside # . But this means that
inside each such object we can find a curve connecting the two largest faces of one of the 2d 3-
blocks. Hence, one of the 3-blocks must be crossed by at least |O #
The next step is to prove a relation between the number of crossing objects and the
number of guards in a 3-block B. The following auxiliary lemma will be called for in the
proof of Lemma 3.3.
Lemma 3.2 For any given hypercube # intersected by a set O of m objects, and any constant
b with 0 < b 6 m, we can identify more than #m/(2 d+1
- 2)b# disjoint hypercubes
inside # each intersected by at least b objects from O.
Proof: We construct a tree on # by recursively identifying between 2 and 2 d subhypercubes
in the current hypercube if it is intersected by at least 2 d b objects. Assume that we have
a hypercube # intersected by at least 2 d b objects and consider its decomposition into 2 d
equal-sized subhypercubes (by means of the d hyperplanes perpendicular to the coordinate
axes and cutting the hypercube into two equal halves). We call a (sub)hypercube crowded
if it is intersected by at least b objects. Note that at least one of the subhypercubes of
# is crowded. Note also that each object intersecting # intersects at least one of the 2 d
subhypercubes (because the objects are d-dimensional and open).
. If the number of crowded subhypercubes of # exceeds one, then each of these crowded
subhypercubes becomes a child of # in our tree. We charge the objects that do not
intersect one of the crowded subhypercubes, to #. The number of such objects is at
most (2 d
. If the number of crowded subhypercubes of # equals one, then this subhypercube # is
shrunk towards the vertex it shares with # until # is intersected by at least (2 d
objects but # is still intersected by at least b objects. (Note that this is always possible
because the objects are d-dimensional.) Now consider the 2 d
hypercubes of maximal
size contained in # and sharing a vertex with # . Since these hypercubes jointly
cover # , at least one of them, say # , is crowded. The crowded hypercubes # and
# become the children of # in our tree. We charge the at most (2 d
objects that do not intersect # or # to # .
The leaves of the resulting tree correspond to disjoint hypercubes that are intersected by
at least b objects. We will see that there are at least m/(2 d+1
leaves.
Let L and I be the number of leaves and internal nodes of the resulting tree, respectively.
As every internal node has at least two children the number of leaves is larger than the number
of internal nodes, so L > I. We notice that the number of objects charged to an internal
node is at most (2 d
- 2)b and the number of objects intersecting a hypercube corresponding
to a leaf is at most 2 d b - 1. Since the number of objects charged to all internal nodes plus
the number of objects intersecting the hypercubes at the leaves should at least be equal to m
we have that
m.
Using the inequality L > I we obtain
Lemma 3.3 Let G be a #-guarding set for a collection O of objects in R d , with d > 2. Let
B be a 3-block crossed by m objects from O, and let # < m. Then there must be at least
d3 d-1 (2 d
guards from G inside B.
Proof: We assume withou loss of generality that the short side of B has unit length. We
l
d3 d-1 (2 d
slices of height 1/l by means of hyperplanes parallel to its two largest faces, which are (d- 1)-
dimensional hypercubes of side length 3. The two largest (and opposite) faces of the resulting
slices are again (d - 1)-dimensional hypercubes of side length 3; see Figure 3 for a three-dimensional
3-block and the l slices. We observe that each of the objects from O crossing B

Figure

3: A 3-block B (with a crossing object shown shaded) is cut into l slices; each slice S
contains a certain number of cubes (sharing a face with the face g of S) that must contain at
least one guard.
also crosses each of the l slices. Consider a slice S and let g be one of its two largest faces.
The intersections with g of the m objects crossing B are (d - 1)-dimensional objects.
Lemma 3.2 states that we can identify at least #m/(2 d
dimensional hypercubes inside g, each of which is intersected by at least #
the (d-1)-dimensional volume of g is 3 d-1 , the number of (d-1)-dimensional hypercubes with
a side length exceeding 1/l is less than (3l) d-1 , so at least #m/(2 d
-2)(#+1)#-(3l) d-1 (which
is positive) of such hypercubes have a side length of 1/l or less. For every such hypercube #,
take the d-dimensional hypercube # with # as a face and contained in the slice S; this is
possible because the side length of # is at most 1/l (see Figure 3). The hypercube # is
intersected by at least # because # is intersected by #
must contain a guard. It follows that we need at least #m/(2 d
per slice, which sums up to a total of
d3 d-1 (2 d
guards for the entire 3-block B.
Combining the two lemmas above, we now prove that the number of relatively large objects
intersecting a hypercube cannot exceed (roughly) the number of guards in its vicinity to the
Theorem 3.4 Let G be a #-guarding set for a set O of objects in R d , with d > 2. Any hyper-cube
whose vicinity contains exactly g guards from G is intersected by O(#(1+g 1-1/d
from O that are at least as large as #.
denote the number of objects at least as large as # intersecting #. From
Lemma 3.1 we know that there is a 3-block B in the vicinity of # that is crossed by at least
curves. Lemma 3.3 now implies that there must be at least
guards in B. Since B is in the vicinity of #, this number must be less than or equal to g,
which (together with the fact that B can still be intersected by # objects if it contains no
guards) implies the theorem.
We now turn our attention to the complexity of motion planning in two-dimensional
workspaces that are either uncluttered or have small simple-cover complexity, and then extend
the obtained results to three dimensions in Section 5.
4 The complexity of motion planning in planar workspaces
Let R be a robot with f degrees of freedom, moving in a two-dimensional workspace amidst a
set O of n obstacles. The robot R can be of any type: it can be a free-flying robot, a robotic
arm, and so on. The only restriction is that it must have bounded reach [16], which is defined
as follows. Let p R be an arbitrary reference point inside R. Then the reach of R, denoted
by reach(R), is defined as the maximum distance that any point of R can be from p R , taken
over all possible configurations of R. For instance, if R consists of two links of length 1 that
are both attached to the origin, and the reference point is the tip of one of the links, then the
reach of R is 2. (If the reference point would be the origin then the reach would be 1. For
any two reference points, however, the two values reach(R) can be at most a factor of two
apart.) A bounded-reach robot is now defined as a robot R with
C#O {size(C)},
where c is a (small) constant.
In this section we study the complexity of the free space of a bounded-reach robot R
under the assumption that the set of obstacles satisfies one of the models defined above. We
prove an # f worst-case lower bound on the free-space complexity for the most
restricted model, namely for #-cluttered scenes. Because unclutteredness implies small simple-
cover complexity in the hierarchy of input models [5], this bound carries over to scenes with
small simple-cover complexity. Moreover, we prove an O(# f ((sn) f/2 + sn)) upper bound for
scenes with a #-guarding set of size s - n. By the conclusions from Section 2, the upper bound
immediately carries over to uncluttered scenes and scenes with small simple-cover complexity.
Hence, in both models we get a tight bound of #(n f/2 n).
4.1 A lower bound for uncluttered scenes
The robot R in our lower bound example consists of f links, which are all attached to the
origin. The links have length 1 #, for a su#ciently small # > 0. Obviously R has f degrees
of freedom.
The set of n obstacles for the case of a 2-cluttered planar scene is defined as follows.
(Later we adapt the construction to get the bound for #-cluttered scenes for larger but still
constant #.) Recall that our obstacles are presumed to be two-dimensional. Fix an integer
(a) (b) (c)
new obstacle #
bounding box
of current scene
the robot

Figure

4: (a) Part of the lower bound construction. (b,c) Adding bounding-box vertices to
make the scene uncluttered.
parameter m; it will turn out later that the appropriate value for m is roughly # n. For a
given integer i, let C i be the horizontal rectangle of length 1 and small height # whose lower
left corner lies on the unit circle and has a y-coordinate equal to i/m-see Figure 4(a) for an
example. Let O 1 := {C i | 1 6 i 6 m}; this set forms a subset of the set of all obstacles. The
remaining obstacles, which we describe later, are only needed to turn the environment into
an uncluttered environment.
Consider any subset of f rectangles from O 1 . It is easy to see that there is a semi-free
placement of R such that each rectangle in the subset is touched by a link of R. Hence,
the free-space complexity is # m f ). When m is large, however, the set O 1 does not form an
uncluttered enviroment: the dashed square in Figure 4(a) for instance,
m) obstacles
without having a bounding-box vertex of one of the rectangles in its interior. This
problem would disappear if between every pair of adjacent horizontal rectangles there would
be a collection of #(m) equal-spaced bounding-box vertices, as in Figure 4(b). If the distance
between consecutive vertices is set to 1/2m then no square without a bounding-box
vertex in its interior will intersect more than one obstacle from O 1 . Notice that in total
we need #(m vertices for this. We cannot add tiny obstacles between the
rectangles to achieve this, because such obstacles would be much smaller than the robot, so
the robot would no longer have bounded reach. There is no need, however, to add obstacles
between the rectangles; we can also create bounding-box vertices there by adding obstacles
outside the current scene. Suppose that we wish to have a bounding-box vertex at a given
point suppose that the current set of obstacles is contained in the rectangle
we add the right triangle # with vertices (p x , y
as an obstacle-see Figure 4(c).
The point p is a bounding-box vertex of #, and # is disjoint from the current set of obstacles.
By iteratively adding obstacles that generate the necessary bounding-box vertices between
the rectangles in O 1 we transform the cluttered environment into an uncluttered one. The
added obstacles are collected in a set O 2 ; our final set of obstacles is O . It is not
di#cult to see that these obstacles form a 2-cluttered environment in this manner: any square
without bounding-box vertices intersects at most one obstacle from O 1 or two obstacles from
O 2 .
We now have a collection of #(m 2 ) obstacles forming a 2-cluttered scene such that the
free-space complexity is # m f ). By choosing a suitable value for m (in the order of # n), we
obtain a collection of n obstacles such that the free-space complexity is # n f/2 ).
To get the general bound we replace each of the m rectangles in the set O 1 by # (even
thinner) rectangles of length 1 that are quite close together. The lower left corners of these
rectangles still lie on the unit circle; the new scene is #-cluttered. It is still possible to choose
the value #, which determines the length of the links of R, small enough such that any f-tuple
of rectangles in the new set O 1 can be touched by a semi-free placement. Hence, the number
of f-fold contacts has increased to # f m f ). By again choosing m to be roughly # n we get a
bound of # f n f/2 ). In the specific case that f = 1 the maximum complexity is
clearly# n).
Theorem 4.1 The free-space complexity of a bounded-reach robot with f degrees of freedom
moving in a two-dimensional #-cluttered scene consisting of n obstacles can be # f n f/2 +n).
4.2 An upper bound for scenes with linear-size guarding sets
We want to prove an upper bound on the complexity of the free space of a bounded-reach
robot with f degrees of freedom moving in a scene with a linear-size #-guarding set. The global
structure of our proof will be as follows. We construct a decomposition of the workspace into
cells that are not much smaller than the robot. The decomposition will have the property that
none of its cells can have too many obstacles close to it. This means that the robot cannot
have too many f-fold contacts when its reference point lies inside any given cell. Summing
the number of f-fold contacts over all the cells using Theorem 3.4 yields the desired bound
on the number of features of the free space.
The decomposition we use is obtained by adapting (the first stage of) the partitioning
scheme described by de Berg [4]. First we describe the exact properties that we require, and
then show how to obtain a decomposition with the desired properties.
reach(R). Define the expansion - o of an object o to be the Minkowski sum of
with a square of size 2# centered at the origin. Hence, -
contains exactly those points that
are at a L# -distance of less than # from o. Note that the expansion of a square # is another
square, whose edge length is 2# more than the edge length of #. Let
O := { b
C | C # O}
denote the set of expanded obstacles.
Lemma 4.2 Let O be a set of obstacles in R 2 (or R 3 ), and let G be a #-guarding set for
O. Then there exists a set S of cells that are either squares (or cubes) or L-shapes with the
following properties:
(P1) the cells in S form a decomposition of a su#ciently large bounding square (or cube) of
the set
O of expanded obstacles;
(P2) the number of cells in S is O(|G|);
every cell in S whose size is greater than 2# is intersected by O(#) expanded obstacles;
every cell in S whose size is less than or equal to 2# is a square (or cube) of size at
least #.
Proof: We prove the lemma for the planar case; the generalization to three dimensions is
straightforward.
Let
G denote the set of points obtained by adding to every guard g # G the four corner
points of the square of size 2# centered at g. The set
G contains 5|G| points. We enclose
O (and
by a su#ciently large square and recursively decompose this square based on the
points of
G, as follows.
Let
G # denote the subset of points from
G contained in the interior of a square # at some
stage in the (quadtree-like) subdivision process. The square # is handled according to the
following set of rules.
1. If size(#) 6 2# or
G # then # is one of the cells in S.
2. If size(#) > 2#,
G #, and not all points of
lie in the interior of a single quadrant
of #, then # is subdivided into four quadrants, which are handled recursively.
3. If size(#) > 2#,
G #, and all points of
lie in the interior of a single quadrant of
#, then # is subdivided as follows. Let # be the smallest square containing the points
from
G # in its closure that shares a vertex with #.
(a) If size(# then # is handled recursively, and the L-shape # is a cell in S.
(b) If size(# ) 6 #, then let # denote a square of size # contained in # and containing # .
The square # and the L-shape # are cells in S.
It follows immediately from the construction that the cells in S satisfy Properties (P1) and
(P4). A subdivision according to rule 2 splits the set
G # into two nonempty subsets; a
subdivision according to rule 3 puts one of the points of
G # onto the boundary of a subcell.
Both subdivisions can therefore be performed at most | b
times. As a result, the number of
cells will be O(|
which proves (P2).
It remains to prove Property (P3). By construction, any cell of size more than 2# contains
no point from
G. We now prove that any square # of size at least # that does not contain any
points from
G intersects at most # expanded obstacles. If the cell under consideration is a
square this immediately proves (P3), and if it is an L-shape then it also proves (P3) because
an L-shape of size at least 2# can be covered by three squares of size at least #. So consider
a square # without points from
G and whose size is at least #. The fact that # contains no
points from
G implies that its expansion -
# contains no guard from G-see Figure 5 for an
illustration. This means that -
# is intersected by at most # original obstacles, which implies
points added for p

Figure

5: A guard from G inside - # implies a point of
G in #.
that # is intersected by at most # expanded obstacles.
Now that we have a suitable decomposition of the workspace, we can use Theorem 3.4 to
prove our main result.
Theorem 4.3 Let R be a bounded-reach robot with f degrees of freedom, with f a constant,
moving in a two-dimensional workspace containing a set O of n obstacles. If the set of obstacles
has a #-guarding set of size s - n, then the complexity of the free space is O(# f ((sn) f/2 +sn)).
Proof: If R touches an obstacle C, its reference point must lie in the interior of
C. (This
is true because we defined # as twice the reach of R.) Therefore we can bound, for any
the number of k-fold contacts of R by bounding the number of k-tuples of
expanded obstacles with a non-empty common intersection. The idea of the proof is to
decompose the workspace according to Lemma 4.2 and then sum the number of k-tuples over
all cells of the decomposition using Theorem 3.4.
Let G be a #-guarding set of size sn for the obstacle set O, and let S denote a decomposition
having the properties stated in Lemma 4.2. To bound the free-space complexity we
have to bound the number of simultaneous contacts involving k obstacles, for
By Property (P1) this means that the free-space complexity is bounded by
f
denotes the number of expanded obstacles intersecting the cell #. The asymptotic
value of this sum is dominated by the term where so we ignore the other terms from
now on. Let S 1 be the subset of S consisting of the cells of size larger than 2#, and let S 2 be
the subset of S consisting of the remaining cells. By Properties (P2) and (P3) we have
Now consider the cells in S 2 . By Property (P4) these cells are squares whose size lies between
# and 2#. Let # be such a square. We claim that the number of expanded obstacles
intersecting # is O(#(1 # is the number of guards from G in the vicinity of
the expansion -
#. It is important to observe that 3# 6 size(-#) 6 4#. Furthermore, any expanded
obstacle intersecting # corresponds to an original obstacle that intersects -
#. Because
# 6 2c - min{size(C) | C # O} for a constant c, we can partition - # into O(1) subsquares whose
size is smaller than the size of the smallest obstacle. By Theorem 3.4, this means that the
number of original obstacles intersecting -
# is O(#(1+ # g # )), where g # is the number of guards
in the vicinity of -
#. Hence, the number of expanded obstacles intersecting # is bounded by
this quantity as well.
We conclude that the number of f-tuples of expanded obstacles with a non-empty common
intersection in a cell of S 2 is bounded by
where g # is the number of guards in the vicinity of the expansion -
#. Since all squares have
size at least # by Property (P4), the vicinity of an expanded square in S 2 intersects O(1) other
vicinities of expanded squares. Hence, a guard from G lies in O(1) vicinities, and we have
which leads to
Therefore the total number of f-fold contacts of R is bounded by
5 The complexity of motion planning in 3D workspaces
Having described the two-dimensional setting in the previous section, we now turn our attention
to a robot R moving in a three-dimensional workspace amidst a set O of n obstacles. As
in the two-dimensional case, the robot is allowed to be of any type-we only require that its
reach is bounded. We prove an # 2f worst-case lower bound on the complexity
of the free space for #-cluttered scenes, and an O(# f ((sn) 2f/3 + sn)) upper bound for scenes
with a #-guarding of size s - n. As before, this results in a tight bound of #(n 2f/3 +n) for uncluttered
scenes. We also prove an # n f ) worst-case lower bound on the complexity of scenes
with small simple-cover complexity. The maximum free-space complexity for such scenes is
therefore #(n f ) and thus equivalent to the complexity for unrestricted scenes.
5.1 Lower bounds
A lower bound for scenes with small simple-cover complexity
We consider the scene consisting of n rings
y, z) |
shown in Figure 6. It was shown [6] that a similar scene consisting
of unit circles has small simple-cover complexity but requires a #-guarding set of
for any constant #. It is clear that these properties carry over to our scene in which the circles
are replaced by thin rings. Our robot R consists of f links, which are all attached to the point
(0, 2, 0). Each link has length 2 and rotates about the axis y, z) |
causing it to stay inside the xy-plane. Note that the size of the robot is comparable to the
size of the obstacles so it has bounded reach. For any subset of f rings, there is a semi-
the robot
x
z
y

Figure

The lower-bound construction.
placement of R such that each ring C i in the subset is touched by a link of R. As a
consequence, the free-space complexity is # n f ).
Theorem 5.1 The free-space complexity of a bounded-reach robot with f degrees of freedom
moving in a three-dimensional scene with small simple-cover complexity consisting of
n obstacles can be # n f ).
A lower bound for uncluttered scenes
Our approach to obtaining a worst-case lower bound for 3D #-cluttered scenes is similar to the
planar case. We fix a parameter m and consider the set O 1 of m 2 thin unit-length rectangloids
y, z) |
#,
Consider the m 2 planes through pairs of obstacles and choose a point
that lies on none of these planes and satisfies 1/2 < x q , y q < 1/2 Our robot R has f
links, which are all anchored at q. Each link has length 1 and is able to rotate about the axis
y, z) | causing it to stay inside the plane z = 1/2; the choice of q
allows it be placed in contact with each obstacle in O 1 . Figure 7(a) shows the intersection of
the scene with the plane z = 1/2. The size of R is comparable to the size of the obstacles in
the robot
x
z
y
x
y
obstacle
(a) (b)
points

Figure

7: (a) Cross-section of the environment at z = 1/2. (b) Magnified portion of the
scene showing a single obstacle and the four sequences of points (bounding-box vertices)
immediately surrounding it.
O 1 . For any subset of f obstacles there is a semi-free placement of R such that each obstacle
C i,j in the subset is touched by a link of R. Hence, the complexity of the free space is # m 2f ).
To prevent cubes from intersecting more than one obstacle from O 1 we put sequences of
points on each of the lines l = {(x, y, z) |
see

Figure

7(b) for one obstacle and the points surrounding it. The distance between two
consecutive points on a single line is again equal to 1/2m. We turn the #(m 3 ) points into
bounding-box vertices by iteratively adding tetrahedral obstacles in a way similar to the
planar case. The resulting #(m 3 ) obstacles are collected in O 2 , and our final set of obstacles
is Any cube without bounding box vertices intersects at most one obstacle
from O 1 or two obstacles from O 2 .
As a result, we now have a collection of #(m 3 ) obstacles forming a 2-cluttered scene with
a free-space complexity of # m 2f ). By choosing the free-space complexity becomes
for the set of n obstacles.
As in the two-dimensional example, we now replace each of the m obstacles in O 1 by
# obstacles that are close together and arranged such that each of them can be touched by
the links of R. The resulting scene is #-cluttered, and the number of f-fold contacts increases
The theorem follows from again choosing
n. By again
choosing m to be roughly n 1/3 we get a bound of # f n 2f/3 ). Again the maximum complexity
is # n) in the case that f = 1.
Theorem 5.2 The free-space complexity of a bounded-reach robot with f degrees of freedom
moving in a three-dimensional #-cluttered scene of n obstacles can be # f
5.2 An upper bound for scenes with linear-size guarding sets
Proving an upper bound on the free-space complexity of a bounded-reach robot with f degrees
of freedom moving in a scene with a linear-size guarding set is entirely analogous to the two-dimensional
case.
Theorem 5.3 Let R be a bounded-reach robot with f degrees of freedom, with f a con-
stant, moving in a three-dimensional workspace containing a set O of n obstacles. If the
set of obstacles has a #-guarding set of size s - n, then the complexity of the free space is
Proof: Analogous to the proof of Theorem 4.3, except that
which yields
6 Conclusion
We have established that the maximum complexity of the free-space of a bounded-reach robot
with f degrees of freedom moving in an uncluttered scene is #(n f/2 +n) in R 2 and #(n 2f/3 +n)
in R 3 ; the planar bound also holds for scenes with small simple-cover complexity. These
bounds fit nicely between the #(n) bound for low-density scenes-which are more restrictive-
, and the #(n f ) bound for unrestricted scenes. Surprisingly, the maximum complexity of the
space for a robot moving in a 3D scene with small simple-cover complexity is equal to
#(n f )-the bound for unrestricted scenes.
Motion planning in low-density environments can be solved in an amount of time that is
almost equal to the maximum free-space complexity [20]. It is interesting to see if a similar
result is possible for uncluttered scenes and scenes with small simple-cover complexity.



--R

Computing depth orders for fat objects and related problems.
Approximate motion planning and the complexity of the boundary of the union of simple geometric figures.
Implementation and extension of the ladder algorithm
Linear size binary space partitions for uncluttered scenes
Realistic input models for geometric algorithms
Guarding scenes against invasive hypercubes
On the union of
Dynamic data structures for fat objects and their applications.


Fat triangles determine linearly many holes

Range searching and point location among fat objects
"piano movers"
Range searching in low-density environments
The complexity of the free space for a robot moving amidst fat obstacles
The complexity of the free space for motion planning amidst fat obstacles
Motion planning amidst fat obstacles.
Motion planning amidst fat obstacles
Motion planning in environments with low obstacle density.
On fatness and fitness-Realistic input models for geometric algorithms
--TR
Efficient hidden surface removal for objects with small union size
Fat Triangles Determine Linearly Many Holes
Motion planning amidst fat obstacles (extended abstract)
The complexity of the free space for a robot moving amidst fat obstacles
Computing depth orders for fat objects and related problems
Range searching and point location among fat objects
Range searching in low-density environments
Realistic input models for geometric algorithms
3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
On the union of <italic>k</italic>-curved objects
Dynamic data structures for fat objects and their applications

--CTR
Mark de Berg , Haggai David , Matthew J. Katz , Mark Overmars , A. Frank van der Stappen , Jules Vleugels, Guarding scenes against invasive hypercubes, Computational Geometry: Theory and Applications, v.26 n.2, p.99-117, October
Esther Moet , Marc van Kreveld , A. Frank van der Stappen, On realistic terrains, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
motion planning;free space complexity;input models