Full text of DOI:10.1016/S0925-7721(01)00022-0

Computational Geometry 23 (2002) 53–68
www.elsevier.com/locate/comgeo
Models and motion planning
a
b,1
a
a,∗
Mark de Berg , Matthew J. Katz , Mark H. Overmars , A. Frank van der Stappen ,
a
Jules Vleugels
a
Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80089, 3508 TB Utrecht, The Netherlands
b
Department of Mathematics and Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel
Received 11 December 2000; accepted 24 April 2001
Communicated by J. Matoušek
Abstract
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/2
f degrees of freedom in the plane is ꢀ(n
+ 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 ꢀ(n2
f/3
+ n). All these bounds fit nicely between the ꢀ(n) bound
f
for the maximum free-space complexity for low-density environments and the ꢀ(n ) bound for unrestricted
environments. Surprisingly—because contrary to the situation in the plane—the maximum free-space complexity
f
is ꢀ(n ) for a three-dimensional environment with small simple-cover complexity.  2002 Elsevier Science B.V.
All rights reserved.
Keywords: Motion planning; Free space complexity; Input models
1. Introduction
It is well known that the maximum complexity of the free space of a robot with f degrees of freedom
f
moving in a scene consisting of n disjoint obstacles of constant complexity can be ꢁ(n ). Consequently,
exact motion-planning algorithms often have a worst-case running time of at least the same order of
*
Corresponding author.
E-mail addresses: markdb@cs.uu.nl (M. de Berg), matya@cs.bgu.ac.il (M.J. Katz), markov@cs.uu.nl (M.H. Overmars),
frankst@cs.uu.nl (A.F. van der Stappen), jules@cs.uu.nl (J. Vleugels).
1
Supported by the Israel Science Foundation founded by the Israel Academy of Sciences and Humanities.
0925-7721/02/$ – see front matter  2002 Elsevier Science B.V. All rights reserved.
PII: S0925-7721(01)00022-0

54
M. de Berg et al. / Computational Geometry 23 (2002) 53–68
magnitude. This is probably one of the reasons that most of the exact algorithms were never implemented.
5
One exception is Bañon’s implementation [3] of the O(n ) 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
f
sensitive to the actual complexity of the free space, and this is in practice far less than the ꢀ(n ) 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. (A 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 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
2
and slightly adapted versions of Schwartz and Sharir’s ladder algorithm run in O(n ) and O(nlogn) time,
respectively, which is more in line with the experimental results of Bañon. Van der Stappen and Overmars
[19] used the linear free-space complexity result to obtain an efficient 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 ꢀ(nf/2 + n) when the workspace is two-dimensional. These
f
bounds fit nicely between the ꢀ(n) bound for low-density scenes and the ꢀ(n ) bound for general
scenes. For three-dimensional uncluttered scenes the bound becomes ꢀ(n2 +n). Contrary to the planar
f/3
case, small simple-cover complexity does not result in a reduced maximum free-space complexity for
f
three-dimensional workspaces: the maximum complexity is ꢀ(n ).
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

M. de Berg et al. / Computational Geometry 23 (2002) 53–68
55
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.
2. Input models
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
d
set in R , 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 difference of a hypercube σ with a hypercube σ ⊆ σ of less than half
d
its size and sharing a vertex with it. An L-shape can be covered by 2 − 1 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.
d
Definition 2.1. Let O be a set of objects in R . We say that O has λ-low-density if for any ball B, the
number of objects P ∈ O with ρ (P ) ꢀ radius(B) that intersect B is at most λ.
i
meb
i
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.
d
Definition 2.2. Let O be a set of objects in R . 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.

56
M. de Berg et al. / Computational Geometry 23 (2002) 53–68
d
Definition 2.3. Let O be a set of m objects in R , 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 sm.
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.
2
Guarding sets [6] against hypercubes 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.
d
Definition 2.4. Let O be a set of objects in R , 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 g 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
d
with respect to its center. Thus, if we partition the vicinity of σ into 5 equal-sized subhypercubes, then
d
σ consists of the 3 middle subhypercubes. The planar case is illustrated in Fig. 1.
d
We will show that the number of objects intersecting a hypercube σ in R and at least as large as σ
cannot be more than (roughly) O(g1
−1/d
), where g is the number of guards in the vicinity of σ.
2
In the paper by de Berg et al. [6] guarding sets are defined against an arbitrary family of ranges. It is sufficient for our
purposes to concentrate on hypercubic ranges.

M. de Berg et al. / Computational Geometry 23 (2002) 53–68
57
Fig. 1. A square σ and its vicinity.
Fig. 2. Illustration of the planar case in the proof of Lemma 3.1.
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
d
m/(2d(3 − 1)) objects.
d
Proof. Partition σ into 3 equal-sized subhypercubes. Each object intersecting σ must intersect one of
d
the 3 − 1 subhypercubes that have a common boundary with σ (because it is at least as large as σ).
∗
d
One of the subhypercubes, say σ , thus intersects at least m/(3 − 1) 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 outer 3-blocks that are contained in Σ , that is, the 3-blocks that have one
∗
∗
of the 2d sides of Σ as a face—see Fig. 2 for an illustration of the planar case. Note that Σ and, hence,
all 2d outer 3-blocks, are contained in the vicinity of σ. We shall argue that one of the outer 3-blocks is
d
crossed by at least m/(2d(3 − 1)) objects.
∗
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 outer 3-blocks. Hence, one of the outer 3-blocks must
∗
d
be crossed by at least |O |/2d = m/(2d(3 − 1)) objects.
✷
The next step is to prove a relation between the number of crossing objects and the number of guards
in a 3-block. 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
d+1
0
< b ꢁ m, we can identify more than ꢁm/(2
− 2)bꢂ disjoint hypercubes inside σ each intersected by
at least b objects from O.

58
M. de Berg et al. / Computational Geometry 23 (2002) 53–68
d
Proof. We construct a tree on σ by recursively identifying between 2 and 2 subhypercubes in the current
d
∗
hypercube if it is intersected by at least 2 b objects. Assume that we have a hypercube σ intersected
d
d
by at least 2 b objects and consider its decomposition into 2 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
d
2
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
∗
d
of the crowded subhypercubes, to σ . The number of such objects is at most (2 − 2)(b − 1).
∗
ꢀ
If the number of crowded subhypercubes of σ equals one, then this subhypercube σ is shrunk
∗
∗
ꢀ
d
towards the vertex it shares with σ until σ \ σ is intersected by at least (2 − 1)b objects but
ꢀ
σ is still intersected by at least b objects. (Note that this is always possible because the objects
d
∗
ꢀ
are d-dimensional.) Now consider the 2 − 1 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
d
d
ꢀ
ꢀꢀ
∗
at most (2 − 1)b − b = (2 − 2)b 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.
d+1
We will see that there are at least m/(2
− 2)b 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,
d
so L > I. We notice that the number of objects charged to an internal node is at most (2 − 2)b and the
d
number of objects intersecting a hypercube corresponding to a leaf is at most 2 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
d
d
I(2 − 2)b + L(2 b − 1) ꢀ m.
Using the inequality L > I we obtain
ꢀ
ꢁ
m
L >
.
✷
d+1
(
2
− 2)b
d
Lemma 3.3. Let G be a κ-guarding set for a collection O of m objects in R , with d ꢀ 2. Let B be a
3
-block crossed by m objects from O, and let κ < m. Then there must be at least
ꢀ
ꢁ
d/(d−1)
m
(
d − 1)3d−1
d−1
d
d3 (2 − 2)(κ + 1)
guards from G inside B.
Proof. We assume, without loss of generality, that the short side of B has unit length. We split B into
ꢀ
ꢁ
1
/(d−1)
m
l :=
d−1
d
d3 (2 − 2)(κ + 1)

M. de Berg et al. / Computational Geometry 23 (2002) 53–68
59
Fig. 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.
(
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 Fig. 3 for a three-dimensional 3-block
and the l slices. We observe that each of the objects from O crossing B 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.
d
Lemma 3.2 states that we can identify at least ꢁm/(2 − 2)(κ + 1)ꢂ disjoint (d − 1)-dimensional
hypercubes inside g, each of which is intersected by at least κ + 1 objects. Since the (d − 1)-dimensional
d−1
volume of g is 3 , the number of (d − 1)-dimensional hypercubes with a side length exceeding 1/l is
d−1
d
d−1
less than (3l) , so at least ꢁm/(2 −2)(κ +1)ꢂ−(3l)
(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 Fig. 3).
ꢀ
The hypercube σ is intersected by at least κ + 1 objects because σ is intersected by κ + 1 objects, and
d
d−1
guards per
hence it must contain a guard. It follows that we need at least ꢁm/(2 − 2)(κ + 1)ꢂ − (3l)
slice, which sums up to a total of
ꢂꢀ
ꢁ
ꢃ
ꢀ
ꢁd/(d−1)
m
m
l
− (3l)d−1 ꢀ (d − 1)3d−1
d
d−1
d
(
2 − 2)(κ + 1)
d3 (2 − 2)(κ + 1)
guards for the entire 3-block B. ✷
Combining the 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 power 1 − 1/d.
d
Theorem 3.4. Let G be a κ-guarding set for a set O of objects in R , with d ꢀ 2. Any hypercube σ whose
1
−1/d
vicinity contains exactly g guards from G is intersected by O(κ(1 + g
least as large as σ.
)) objects from O that are at
Proof. Let m denote the number of objects at least as large as σ intersecting σ. From Lemma 3.1 we
d
know that there is a 3-block B in the vicinity of σ that is crossed by at least m/(2d(3 − 1)) object
curves. Lemma 3.3 now implies that there must be at least
ꢀ
ꢁd/(d−1)
m
(
d − 1)3d−1
d−1
d
d
2
d23 (3 − 1)(2 − 2)(κ + 1)

60
M. de Berg et al. / Computational Geometry 23 (2002) 53–68
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 be an
R
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 , taken over all possible configurations of R. For instance,
R
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
ꢄ
ꢅ
reach(R) ꢁ c · min size(C) ,
C∈O
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
f
f/2
assumption that the set of obstacles satisfies one of the models defined above. We prove an ꢁ(κ n +n)
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,
f
f/2
we prove an O(κ ((sn) + 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
f/2
with small simple-cover complexity. Hence, in both models we get a tight bound of ꢀ(n + 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 sufficiently 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 parameter m; it will turn out later that
√
the appropriate value for m is roughly n. For a given integer i, let C be the horizontal rectangle of
i
ꢀ
length 1 and small height ε whose lower left corner lies on the unit circle and has a y-coordinate equal
to i/m—see Fig. 4(a) for an example. Let O := {C | 1 ꢁ i ꢁ m}; this set forms a subset of the set of
1
i
all obstacles. The remaining obstacles, which we describe later, are only needed to turn the environment
into an uncluttered environment.

M. de Berg et al. / Computational Geometry 23 (2002) 53–68
61
Fig. 4. (a) Part of the lower bound construction. (b), (c) Adding bounding-box vertices to make the scene uncluttered.
Consider any subset of f rectangles from O . It is easy to see that there is a semi-free placement of
1
R such that each rectangle in the subset is touched by a link of R. Hence, the free-space complexity
f
is ꢁ(m ). When m is large, however, the set O does not form an uncluttered environment: the dashed
1
square in Fig. 4(a) for instance, intersects ꢁ(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 Fig. 4(b). If
the distance between consecutive vertices is set to 1/2m then no square without a bounding-box vertex in
2
its interior will intersect more than one obstacle from O . Notice that in total we need ꢀ(m ) bounding-
1
box 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 p = (p , p ), and suppose that the current set of obstacles is contained in the
x
y
rectangle [x , x ]×[y , y ]. Then we add the right triangle ∆ with vertices (p , y +x −p ),
min max
min max
x
max
max
x
(
x
max
+y −p , p ) and (x +y −p , y +x −p ) as an obstacle—see Fig. 4(c). The point p
max
y
y
max
max
y
max
max
x
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 we transform
1
the cluttered environment into an uncluttered one. The added obstacles are collected in a set O ; our
2
final set of obstacles is O = O ∪ O . It is not difficult to see that these obstacles form a 2-cluttered
1
2
environment in this manner: any square without bounding-box vertices intersects at most one obstacle
from O or two obstacles from O .
1
2
2
We now have a collection of ꢀ(m ) obstacles forming a 2-cluttered scene such that the free-space
√
f
complexity is ꢁ(m ). By choosing a suitable value for m (in the order of n), we obtain a collection of
f/2
n obstacles such that the free-space complexity is ꢁ(n ).
To get the general bound we replace each of the m rectangles in the set O by κ (even thinner)
1
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 can be
1
f
f
touched by a semi-free placement. Hence, the number of f -fold contacts has increased to ꢁ(κ m ). By
√
f
f/2
again choosing m to be roughly n we get a bound of ꢁ(κ n ). 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
f
f/2
a two-dimensional κ-cluttered scene consisting of n obstacles can be ꢁ(κ n + n).

62
M. de Berg et al. / Computational Geometry 23 (2002) 53–68
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.
Let ρ := 2 · reach(R). Define the expansion oˆ of an object o to be the Minkowski sum of o with a
square of size 2ρ centered at the origin. Hence, oˆ 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 := {C | C ∈ O} denote the set of expanded obstacles.
2
3
Lemma 4.2. Let O be a set of obstacles in R (or R ), 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 sufficiently large bounding square (or cube) of the set O
of expanded obstacles;
(
(
(
P2) the number of cells in S is O(|G|);
P3) every cell in S whose size is greater than 2ρ is intersected by O(κ) expanded obstacles;
P4) 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 G) by a sufficiently
ꢆ
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(σ) ꢁ 2ρ or G = ∅ then σ is one of the cells in S.
σ
ꢆ
ꢆ
2. If size(σ) > 2ρ, G
ꢃ
σ
σ
is subdivided into four quadrants, which are handled recursively.
ꢆ
ꢆ
3. If size(σ) > 2ρ, G
ꢃ
σ
σ
ꢀ
ꢆ
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(σ ) ꢁ ρ, then let σ denote a square of size ρ contained in σ and containing σ . The
ꢀ
ꢀ
ꢀꢀ
square σ and the L-shape σ \ σ are cells in S.

M. de Berg et al. / Computational Geometry 23 (2002) 53–68
63
ꢆ
Fig. 5. A guard from G inside ꢆσ implies a point of G in σ.
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 |G| times. As a result, the number of cells will be O(|G|) = O(|G|), 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 Fig. 5 for an illustration. This means that ꢆσ is intersected by at most κ original obstacles,
which implies 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
f
f/2
set of size s · n, then the complexity of the free space is O(κ ((sn) + 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 1 ꢁ k ꢁ f , 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 k = 1, ..., f . By property (P1) this means that the
free-space complexity is bounded by
f
ꢇ ꢇ
k
σ
n ,
k=1 σ∈S
where n denotes the number of expanded obstacles intersecting the cell σ. The asymptotic value of this
σ
sum is dominated by the term where k = f , so we ignore the other terms from now on. Let S be the
1

64
M. de Berg et al. / Computational Geometry 23 (2002) 53–68
subset of S consisting of the cells of size larger than 2ρ, and let S be the subset of S consisting of the
2
remaining cells. By properties (P2) and (P3) we have
ꢇ
ꢈ
ꢉ
f
σ
f
n = O snκ
.
σ∈S1
Now consider the cells in S . By property (P4) these cells are squares whose size lies between ρ and 2ρ.
2
√
Let σ be such a square. We claim that the number of expanded obstacles intersecting σ is O(κ(1+ g )),
σ
where g is the number of guards from G in the vicinity of the expansion ꢆσ. It is important to observe
σ
that 3ρ ꢁ size(ꢆσ) ꢁ 4ρ. Furthermore, any expanded obstacle intersecting σ corresponds to an original
obstacle that intersects ꢆσ. Because ρ ꢁ 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 is bounded by
2
ꢇ
ꢇ
ꢈ ꢈ
√
ꢉꢉ
f
f
σ
n =
κ 1 + gσ
,
σ∈S2
σ∈S2
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 intersects O(1) other vicinities of expanded
2
squares. Hence, a guard from G lies in O(1) vicinities, and we have
ꢇ
gσ = O(sn),
σ∈S2
which leads to
ꢇ
ꢈ ꢈ
√g ꢉꢉ
ꢈ
ꢉ
f
f
f/2
κ 1 +
= O κ (sn)
.
σ
σ∈S2
Therefore the total number of f -fold contacts of R is bounded by
ꢇ
ꢇ
ꢈ
ꢈ
ꢉꢉ
f
σ
f
σ
f
f/2
n +
n = O κ (sn) + sn .
✷
σ∈S1
σ∈S2
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
2
f
2f/3
prove an ꢁ(κ n
+ n) worst-case lower bound on the complexity of the free space for κ-cluttered
f
2f/3
scenes, and an O(κ ((sn)
this results in a tight bound of ꢀ(n
lower bound on the complexity of scenes with small simple-cover complexity. The maximum free-space
complexity for such scenes is therefore ꢀ(n ) and thus equivalent to the complexity for unrestricted
+sn)) upper bound for scenes with a κ-guarding set of size s ·n. As before,
2
f/3
f
+ n) for uncluttered scenes. We also prove an ꢁ(n ) worst-case
f
scenes.

M. de Berg et al. / Computational Geometry 23 (2002) 53–68
65
Fig. 6. The lower-bound construction.
5.1. Lower bounds
5.1.1. A lower bound for scenes with small simple-cover complexity
We consider the scene consisting of n rings,
ꢊ
ꢋ
ꢋ
ꢋ
ꢋ
ꢌ
i
i
2
2
C := (x, y, z)
< x < + ε, 1 < y + z < 1 + ε ,
i
n
n
with 0 ꢁ i < n and small ε shown in Fig. 6. It was shown [6] that a similar scene consisting of unit
2
circles has small simple-cover complexity but requires a κ-guarding set of size ꢁ(n ) 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 h = {(x, y, z) | x = 0, y = 2}, 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-free placement of R such that each ring C in the subset is touched by a link of R.
i
f
As a consequence, the free-space complexity is ꢁ(n ).
Theorem 5.1. The free-space complexity of a bounded-reach robot with f degrees of freedom moving in
f
a three-dimensional scene with small simple-cover complexity consisting of n obstacles can be ꢁ(n ).
5.1.2. A lower bound for uncluttered scenes
Our approach to obtaining a worst-case lower bound for 3D κ-cluttered scenes is similar to the planar
2
case. We fix a parameter m and consider the set O of m thin unit-length rectangloids,
1
ꢊ
ꢋ
ꢋ
ꢋ
ꢋ
ꢌ
i
i
< x < + ε,
m
j
j
Ci,j = (x, y, z)
< y < + ε, 0 < z < 1 ,
m
m
m
for 0 ꢁ i, j < m.
2
Consider the m planes through pairs of obstacles and choose a point q = (x , y , 1/2) that lies on
q
q
none of these planes and satisfies 1/2 < x , y < 1/2 + 1/m. Our robot R has f links, which are all
q
q
anchored at q. Each link has length 1 and is able to rotate about the axis h = {(x, y, z) | x = x , y = y },
q
q
causing it to stay inside the plane z = 1/2; the choice of q allows it be placed in contact with each obstacle

66
M. de Berg et al. / Computational Geometry 23 (2002) 53–68
Fig. 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.
in O . Fig. 7(a) shows the intersection of the scene with the plane z = 1/2. The size of R is comparable
1
to the size of the obstacles in O . For any subset of f obstacles there is a semi-free placement of R such
1
that each obstacle C in the subset is touched by a link of R. Hence, the complexity of the free space
i,j
2
f
is ꢁ(m ).
To prevent cubes from intersecting more than one obstacle from O we put sequences of points on
1
each of the lines l = {(x, y, z) | x = (2i − 1)/2m, y = (2j − 1)/2m} for 0 ꢁ i, j ꢁ m, see Fig. 7(b)
for one obstacle and the points surrounding it. The distance between two consecutive points on a single
3
line is again equal to 1/2m. We turn the ꢀ(m ) points into bounding-box vertices by iteratively adding
3
tetrahedral obstacles in a way similar to the planar case. The resulting ꢀ(m ) obstacles are collected
in O , and our final set of obstacles is O = O ∪ O . Any cube without bounding box vertices intersects
2
1
2
at most one obstacle from O or two obstacles from O .
1
2
3
As a result, we now have a collection of ꢀ(m ) obstacles forming a 2-cluttered scene with a free-space
complexity of ꢁ(m ). By choosing m = n , the free-space complexity becomes ꢁ(n ) for the set
2
f
1/3
2f/3
of n obstacles.
As in the two-dimensional example, we now replace each of the m obstacles in O by κ obstacles
1
that are close together and arranged such that each of them can be touched by the links of R. The
2
f
f
2f
resulting scene is κ-cluttered, and the number of f -fold contacts increases from ꢁ(m ) to ꢁ(κ m ).
√
3
1/3
The theorem follows from again choosing m = n. By again choosing m to be roughly n we get a
f
2f/3
bound of ꢁ(κ n ). 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
f
2f/3
a three-dimensional κ-cluttered scene of n obstacles can be ꢁ(κ n
.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
+ n).
5
freedom moving in a scene with a linear-size guarding set is entirely analogous to the two-dimensional
case.

M. de Berg et al. / Computational Geometry 23 (2002) 53–68
67
Theorem 5.3. Let R be a bounded-reach robot with f degrees of freedom, with f a constant, moving in
a three-dimensional workspace containing a set O of n obstacles. If the set of obstacles has a κ-guarding
f
2f/3
set of size s · n, then the complexity of the free space is O(κ ((sn)
+ sn)).
Proof. Analogous to the proof of Theorem 4.3, except that
ꢇ
ꢇ
ꢈ ꢈ
ꢉꢉ
ꢈ
ꢉ
f
f
σ
2/3
f
2f/3
n =
κ 1 + gσ
= O κ (sn)
,
σ∈S2
σ∈S2
which yields
ꢇ
ꢇ
ꢈ
ꢈ
ꢉꢉ
f
f
σ
f
2f/3
n +
n = O κ (sn)
+ sn .
✷
σ
σ∈S1
σ∈S2
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 ꢀ(nf/2 + n) in R and ꢀ(n
2
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 ) bound for
f
unrestricted scenes. Surprisingly, the maximum complexity of the free space for a robot moving in a
f
3
D scene with small simple-cover complexity is equal to ꢀ(n )—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.
References
[
[
[
1] P.K. Agarwal, M.J. Katz, M. Sharir, Computing depth orders for fat objects and related problems, Computational
Geometry 5 (1995) 187–206.
2] H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. Näher, S. Schirra, C. Uhrig, Approximate motion planning and the
complexity of the boundary of the union of simple geometric figures, Algorithmica 8 (1992) 391–401.
3] J.M. Bañon, Implementation and extension of the ladder algorithm, in: Proc. IEEE Internat. Conf. Robot. Autom., 1990,
pp. 1548–1553.
[
[
4] M. de Berg, Linear size binary space partitions for uncluttered scenes, Algorithmica 28 (2000) 353–366.
5] M. de Berg, M.J. Katz, A.F. van der Stappen, J. Vleugels, Realistic input models for geometric algorithms, in: Proc. 13th
Annu. ACM Sympos. Comput. Geom., 1997, pp. 294–303.
[
6] M. de Berg, H. David, M.J. Katz, M. Overmars, A.F. van der Stappen, J. Vleugels, Guarding scenes against invasive
hypercubes, Technical Report UU-CS-2000-40, Institute of Information and Computing Sciences, Utrecht University,
Utrecht, The Netherlands, 2000.
[
[
7] A. Efrat, M.J. Katz, On the union of κ-curved objects, Computational Geometry 14 (1999) 241–254.
8] A. Efrat, M.J. Katz, F. Nielsen, M. Sharir, Dynamic data structures for fat objects and their applications, Computational
Geometry 15 (2000) 215–227.
[
9] M.J. Katz, 3-D Vertical ray shooting and 2-d point enclosure, range searching, and arc shooting amidst convex fat objects,
Computational Geometry 8 (1997) 299–316.
[
10] M.J. Katz, M.H. Overmars, M. Sharir, Efficient hidden surface removal for objects with small union size, Computational
Geometry 2 (1992) 223–234.

68
M. de Berg et al. / Computational Geometry 23 (2002) 53–68
[
11] J. Matoušek, J. Pach, M. Sharir, S. Sifrony, E. Welzl, Fat triangles determine linearly many holes, SIAM J. Comput. 23
1994) 154–169.
(
[
[
12] J.S.B. Mitchell, D.M. Mount, S. Suri, Query-sensitive ray shooting, Internat. J. Comput. Geom. Appl. 7 (1997) 317–347.
13] M.H. Overmars, A.F. van der Stappen, Range searching and point location among fat objects, J. Algorithms 21 (1996)
629–656.
[
14] J.T. Schwartz, M. Sharir, On the “piano movers” problem I: The case of a two-dimensional rigid polygonal body moving
amidst polygonal barriers, Commun. Pure Appl. Math. 36 (1983) 345–398.
[
[
15] O. Schwarzkopf, J. Vleugels, Range searching in low-density environments, Inform. Process. Lett. 60 (1996) 121–127.
16] A.F. van der Stappen, D. Halperin, M.H. Overmars, The complexity of the free space for a robot moving amidst fat
obstacles, Computational Geometry 3 (1993) 353–373.
[
[
[
[
[
17] A.F. van der Stappen, The complexity of the free space for motion planning amidst fat obstacles, J. Intell. Robotic Syst. 11
(
1994) 21–44.
18] A.F. van der Stappen, Motion planning amidst fat obstacles, Ph.D. Thesis, Department of Computer Science, Utrecht
University, Utrecht, The Netherlands, 1994.
19] A.F. van der Stappen, M.H. Overmars, Motion planning amidst fat obstacles, in: Proc. 10th Annu. ACM Sympos. Comput.
Geom., 1994, pp. 31–40.
20] A.F. van der Stappen, M.H. Overmars, M. de Berg, J. Vleugels, Motion planning in environments with low obstacle density,
Discrete Comput. Geom. 20 (1998) 561–587.
21] J. Vleugels, On fatness and fitness—Realistic input models for geometric algorithms, Ph.D. Thesis, Department of
Computer Science, Utrecht University, Utrecht, The Netherlands, 1997.