Nice point sets can have nasty Delaunay triangulations.
We consider the complexity of Delaunay triangulations of sets of point s in $\Real^3$ under certain practical geometric constraints. The \emph{spread} of a set of points is the ratio between the longest and shortest pairwise distances.  We show that in the worst case, the Delaunay triangulation of $n$ points in~$\Real^3$ with spread $\Delta$ has complexity $\Omega(\min\set{\Delta^3, n\Delta, n^2})$ and $O(\min\set{\Delta^4, n^2})$.  For the case our lower bound construction consists of a uniform sample of a smooth convex surface with bounded curvature.  We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.
Introduction
Delaunay triangulations and Voronoi diagrams are used as a fundamental tool in several geometric
application areas, including nite-element mesh generation [17, 25, 37, 40], deformable surface
modeling [16], and surface reconstruction [1, 3, 4, 5, 12, 35]. Many algorithms in these application
domains begin by constructing the Delaunay triangulation of a set of n points in IR 3 . Delaunay triangulations
can have
complexity
in the worst case, and as a result, all these algorithms have
worst-case running
time
(n 2 ). However, this behavior is almost never observed in practice except
for highly-contrived inputs. For all practical purposes, three-dimensional Delaunay triangulations
appear to have linear complexity.
One way to explain this frustrating discrepancy between theoretical and practical behavior
would be to identify geometric constraints that are satised by real-world input and to analyze
Delaunay triangulations under those constraints. These constraints would be similar to the realistic
input models such as fatness or simple cover complexity [8, 46], which many authors have used
to develop geometric algorithms with good practical performance. Unlike these works, however,
our (immediate) goal is not to develop new algorithms, but rather to formally explain the good
practical performance of existing code.
Portions of this work were done while the author was visiting INRIA, Sophia-Antipolis, with the support of a
UIUC/CNRS/INRIA travel grant. This research was also partially supported by a Sloan Fellowship and by NSF
CAREER grant CCR-0093348. An extended abstract of this paper was presented at the 17th Annual ACM Symposium
on Computational Geometry [30]. See http://www.cs.uiuc.edu/~jee/pubs/spread.html for the most recent
version of this paper.
Dwyer [23, 24] showed that if a set of points is generated uniformly at random from the unit
its Delaunay triangulation has linear expected complexity. Golin and Na [33] recently derived
a similar result for random points on the surface of a three-dimensional convex polytope with constant
complexity. Although these results are encouraging, they are unsatisfying as an explanation
of practical behavior. Real-world point data generated by laser range nders, digital cameras,
tomographic scanners, and similar input devices is often highly structured.
This paper considers the complexity of Delaunay triangulations under two types of practical
geometric constraints. First, in Section 2, we consider the worst-case Delaunay complexity as
a function of both the number of points and the spread|the ratio between its diameter and
the distance between its closest pair. For any n and , we construct a set of n points with
spread  whose Delaunay triangulation has
complexity
n),
our lower bound construction consists of a grid-like sample of a right circular cylinder with constant
height and radius. We also show that the worst-case complexity of a Delaunay triangulation is
We conjecture that our lower bounds are tight, and sketch a possible technique to
improve our upper bounds.
An important application of Delaunay triangulations that has received a lot of attention recently
is surface reconstruction: Given a set of points from a smooth surface , reconstruct an
approximation of . Several algorithms provably reconstruct surfaces if the input points satisfy
certain sampling conditions [4, 5, 12, 35]. In Section 3, we consider the complexity of Delaunay
triangulations of good samples of smooth surfaces. Not surprisingly, oversampling almost any surface
can produce a point set whose Delaunay triangulation has quadratic complexity. We show
that even surface data with no oversampling can have quadratic Delaunay triangulations and that
there are smooth surfaces where every good sample has near-quadratic Delaunay complexity. We
also derive similar results for randomly distributed points on non-convex smooth surfaces. An
important tool in our proofs is the denition of sample measure, which measures the intrinsic
di-culty of sampling a smooth surface for reconstruction.
Throughout the paper, we analyze the complexity of three-dimensional Delaunay triangulations
by counting the number of edges. Two points are joined by an edge in the Delaunay triangulation
of a set S if and only if they lie on a sphere with no points of S in its interior. Euler's formula
implies that any three-dimensional triangulation with n vertices and e edges has at most 2e - 2n
triangles and e - n tetrahedra, since the link of every vertex is a planar graph.
We dene the spread  of a set of points (also called the distance ratio [18]) as the ratio between the
longest and shortest pairwise distances. In this section, we derive upper and lower bounds on the
worst-case complexity of the Delaunay triangulation of a point set in IR 3 , as a function of both the
number of points and the spread. The spread is minimized at (n 1=3 ) when the points are packed
into a tight lattice, in which case the Delaunay triangulation has only linear complexity. On the
other hand, all known examples of point sets with quadratic-complexity Delaunay triangulations,
such as points on the moment curve or a pair of skew lines, have
spread
(n). Thus, it is natural to
ask how the complexity of the Delaunay triangulation changes as the spread varies between these
two extremes.
The spread of a set of points is loosely related to its dimensionality. If a set uniformly covers a
Nice Point Sets Can Have Nasty Delaunay Triangulations 3
bounded region of space, a surface of bounded curvature, or a curve of bounded curvature, its spread
is respectively (n 1=3 ), (n 1=2 ), or (n). The case of surface data is particularly interesting in light
of numerous algorithms that reconstruct surfaces using a subcomplex of the Delaunay triangulation.
We will discuss surface reconstruction in more detail in the next section. Indyk et al. [36] observed
that molecular data usually has sublinear spread, by examining a database of over 100,000 small
drug molecules.
Several algorithmic and combinatorial bounds are known that depend favorably on spread,
especially for dense point sets; a d-dimensional point set is dense if its spread is O(n 1=d ). Edelsbrunner
et al. [28] showed that a dense point set in the plane has at most O(n 7=6 ) halving lines 1 ,
and a dense point set in IR 3 has at most O(n 7=3 ) halving planes. The best upper bounds known
for arbitrary point sets are O(n 4=3 ) [19] and O(n 5=2 ) [41], respectively. Valtr [42, 43, 44] proved
several other combinatorial bounds for dense planar sets that improve the corresponding worst-case
bounds. Verbarg [45] describes an e-cient algorithm to nd approximate center points in
dense point sets. Cardoze and Schulman [14], Indyk et al. [36], and Gavrilov et al. [31] describe
algorithms for approximate geometric pattern matching whose running times depend favorably on
the spread of the input set. Clarkson [18] describes data structures for nearest neighbor queries in
arbitrary metric spaces which are e-cient if the spread of the input is small.
Although our results are described in terms of spread, they also apply to other more robust
quality measures. For example, we could dene the average spread of a point set as the average
(in some sense), over all points p, of the ratio between the distances from p to its farthest and
nearest neighbors. In each of our constructions, the distance ratios of dierent points dier by at
most a small constant factor, so our results apply to average spread as well.
2.1 Lower Bounds
The crucial special case of our lower bound construction is
n). For any positive integer x,
let [x] denote the set f1; xg. Our construction consists of n evenly spaced points on a helical
space curve:
2k
sin

Figure

1. S p n is a grid-like uniform "-sample (see Section 3) of a right circular cylinder, where
1=n). By adding additional points on two hemispherical caps at the ends of the cylinder,
we can extend S p
n into a uniform "-sample of a smooth convex surface with bounded curvature
and constant local feature size. The closest pair of points in S p
n has distance 2=
the diameter of S p
n is 2-o(1), so the spread of S p
n is
n-o(1). We will show that the Delaunay
triangulation of S p
n has
complexity
(n 3=2 ).
Let h (t) denote the helix (t; cos t; sin t), where the parameter  > 0 is called the pitch. The
combinatorial structure of the Delaunay triangulation depends entirely on the signs of certain
insphere determinants. Using elementary trigonometric identities and matrix operations, we can
1 Edelsbrunner et al. [28] only prove the upper bound O(n 5=4 = log  n); the improved bound follows immediately
from their techniques and Dey's more recent O(n 4=3 ) worst-case bound [19].

Figure

1. A set of n points whose Delaunay triangulation has
complexity
simplify the insphere determinant for ve points on this helix as follows.
We obtain the surprising observation that changing the pitch  does not change the combinatorial
structure of the Delaunay triangulation of any set of points on the helix. (More generally, scaling
any set of points on any circular cylinder along the cylinder's axis leaves the Delaunay triangulation
invariant.) Thus, for purposes of analysis, it su-ces to consider the case
(t; cos t; sin t).
Our rst important observation is that any set of points on a single turn of any helix has a
neighborly Delaunay triangulation, meaning that every pair of points is connected by a Delaunay
edge. For any real value t, dene the bitangent sphere (t) to be the unique sphere passing
through h(t) and h(-t) and tangent to the helix at those two points.
Lemma 2.1. For any 0 < t < , the sphere (t) intersects the helix h only at its two points of
tangency.
Proof: Symmetry considerations imply that the bitangent sphere must be centered on the y-axis,
so it is described by the equation x constants a and r. Let
denote
the intersection curve of (t) and the cylinder y Every intersection point between (t)
and the helix must lie on
. If we project the helix and the intersection curve to the xy-plane,
we obtain the sinusoid a portion of the parabola
These two curves meet tangentially at the points (t; cos t) and (-t; cos t).
The mean value theorem implies that
cos x at most four times in the range - < x < .
(Otherwise, the curves y
would intersect more than twice in that
range.) Since the curves meet with even multiplicity at two points, those are the only intersection
points in the range - < x < . Since
(x) is concave, we have
are no intersections with jxj  . Thus, the curves meet only at their two points of tangency.
Corollary 2.2. Any set S of n points on the helix h(t) in the range - < t <  has a neighborly
Delaunay triangulation.
Nice Point Sets Can Have Nasty Delaunay Triangulations 5

Figure

2. The intersection curve of the cylinder and a bitangent sphere projects to a parabola on the xy-plane.
Proof: Let p and q be arbitrary points in S, and let  be the unique ball tangent to the helix at
p and q. By Lemma 2.1,  does not otherwise intersect the helix and therefore contains no point
in S. Thus, p and q are neighbors in the Delaunay triangulation of S.
We can now easily complete the analysis of our helical point set S p
n . Lemma 2.1 implies that
every point in S p
n is connected by a Delaunay edge to every other point less than a full turn
around the helix h p
1=n (t). Each full turn of the helix contains at least b
points. Thus, except
for points on the rst and last turn, every point has at least 2b
Delaunay neighbors, so the
total number of Delaunay edges is more than 2b p nc(n - 2b p nc) > 2n 3=2 - 4n. This crude lower
bound does not count Delaunay edges in the rst and last turns of the helix, nor edges that join
points more than one turn apart. It is not di-cult to show that there are at most O(n) uncounted
Delaunay edges if
n is an integer [29] and at most O(n 3=2 ) uncounted edges in general.
Theorem 2.3. For any n, there is a set of n points in IR 3 with spread
whose Delaunay triangulation
has
complexity
(n 3=2 ). Moreover, this point set is a uniform sample of a smooth convex
surface with constant local feature size.
We generalize our helix construction to other values of the spread  as follows.
Theorem 2.4. For any n and
(n 1=3 ), there is a set of n points in IR 3 with spread  whose
Delaunay triangulation has
complexity
Proof: There are three cases to consider, depending on whether the spread is at least n, between
n and n, or at most
n. The rst case is trivial.
For the case
a set of evenly spaced points on a helix with pitch =n:
2k
sin
Every point in S is connected by a Delaunay edge to every other point less than a full turn away on
the helix, and each turn of the helix
contains
points, so the total complexity of the Delaunay
triangulation
is
(n).
The nal case n 1=3
p n is somewhat more complicated. Our point set consists of several
copies of our helix construction, with the helices positioned at the points of a square lattice, so the
construction loosely resembles a mattress. Specically,
2k
r
sin
6 Je Erickson
where r and w are parameters to be determined shortly. This set contains points. The
diameter of S is (w) and the closest pair distance is (1=
r), so its spread is
r).
Thus, given n and , we have
To complete our analysis, we need to show that Delaunay circumspheres from one helix do not
interfere signicantly with nearby helices. Let  (t) denote the sphere tangent to the helix h at
h (t) and h(-t), for some 0 <   1 and 0 < t  =2. We claim that the radius of this sphere
is less than 3. Since  (t) is centered on the y-axis (see Lemma 2.1), we can compute its radius
by computing its intersection with the y-axis. The intersection points satisfy the determinant
equation
0:
For any  > 0 and t > 0, this equation simplies to
which implies that the radius of  (t) is
s
sin
We easily verify that this is an increasing function of both  and t in the range of interest. Thus,
to prove our claim, it su-ces to observe that the radius of  1 (=2) is
Since adjacent helices are separated by distance 6, every point in S is connected by a Delaunay
edge to every point at most half a turn away in the same helix. Each turn of each helix contains
r) points, so the Delaunay triangulation of S has
complexity
(n
r)
2.2 Upper Bounds
Let B be a ball of radius R in be balls of radius at least r, where
Our upper bound proof uses geometric properties of the 'Swiss cheese'

Figure

3(a). In our upper bound proofs, B will be a ball that contains a subset of the points,
and each b i will be an empty circumsphere of some Delaunay edge.
Lemma 2.5. The surface area of C is O(R 3 =r).
Proof: The outer surface @C \ @B clearly has area O(R 2 su-ces to bound the
surface area of the 'holes'. For each i, let H be the boundary of the ith hole, and
@B. For any point x 2 H, let s x denote the open line segment of length r
extending from x towards the center of the ball b i with x on its boundary. (If x lies on the surface
of more than one b i , choose one arbitrarily.) Let
x2H s x be the union of all such segments,
and for each i, let S
s x . Each S i is a fragment of a spherical shell of thickness r inside
the ball b i . See Figure 3(b).
Nice Point Sets Can Have Nasty Delaunay Triangulations 7
(a) (b)

Figure

3. (a) Swiss cheese (in IR 2 ). (b) Shell fragments used to bound its surface area.
We can bound the volume of each shell fragment S i as follows:
r
where r i  r is the radius of b i . The triangle inequality implies that s x and s y are disjoint for any
two points x; y 2 H, so the shell fragments S i are pairwise disjoint. Finally, since S ts inside a
ball of radius R its volume is O(R 3 ). Thus, we have
r
At this point, we would like to argue that any unit ball whose center is on the boundary
of C contains a constant amount of surface area of C, so that we can apply a packing argument.
Unfortunately, C might contain isolated components and thin handles with arbitrarily small surface
area (like the small triangular component in Figure 3(a)). Thus, we consider balls centered slightly
away from the boundary of C.
Lemma 2.6. Let U be any unit ball whose center is in C and at distance 2=3 from @C. Then U
contains
(1) surface area of C.
Proof: Without loss of generality, assume that U is centered at the origin and that (0; 0; 2=3) is
the closest point of @C to the origin. Let U 0 be the open ball of radius 2=3 centered at the origin,
let V be the open unit ball centered at (0; 0; 5=3), and let W be the cone whose apex is the origin
and whose base is the circle @U \ @V. See Figure 4. U 0 lies entirely inside C, and since r  1, we
easily observe that V lies entirely outside C. Thus, the surface area of @C\W  @C\U is at least
the area of the spherical cap @U 0 \ W, which is exactly 4=27.
Theorem 2.7. Let S be a set of points in IR 3 whose closest pair is at distance 2, and let r be any
real number. Any point in S has O(r 2 ) Delaunay neighbors at distance at most r.
Proof: Let o be an arbitrary point in S, and let B be a ball of radius r centered at o. Call a
Delaunay neighbor of o a friend if it lies inside B, and call a friend q interesting if there is another
8 Je Erickson
U
U'

Figure

4. Proof of Lemma 2.6
point necessarily a Delaunay neighbor of o) such that jopj < joqj and \poq < 1=r. A
simple packing argument implies that o has at most O(r 2 ) boring friends.
Let q be an interesting friend of o, and let p be a point that makes q interesting, as described
above. Since q is a Delaunay neighbor of o, there is a ball d q that has o and q on its boundary
and no points of S in its interior. In particular, p is outside d q , so the radius of d q is greater
than the radius of the circle passing through o, p, and q. Let c be the center of this circle. Since
\poq < 1=r, we must have \pcq < 2=r, and since jpqj  2, we must have jcqj > r. See Figure 5.
We have just shown that the radius of d q is at least r.
<1/r
<2/r
c

Figure

5. The radius of any interesting Delaunay ball is at least r.
For every interesting friend q, let b q be the ball concentric with d q with radius 2=3 less than
the radius of d q , and let U q be the unit-radius ball centered at q. We now have a set of unit balls,
one for each interesting friend of o, whose centers lie at distance exactly 2=3 from the boundary
of the Swiss cheese
2.5, C has surface area O(r 2 ), and by Lemma 2.6,
each unit ball U q
contains
(1) surface area of C. Since the unit balls are disjoint, it follows that
has at most O(r 2 ) interesting friends.
Theorem 2.8. Let S be a set of points in IR 3 whose closest pair is at distance 2 and whose diameter
is 2, and let r be any real number. There are O( 3 =r) points in S with a Delaunay neighbor at
distance at least r.
Proof: Call a point far-reaching if it has a Delaunay neighbor at distance at least r, and let Q
be the set of far-reaching points. Let B be a ball of radius 2 containing S. For each q 2 Q, let
f q be a maximal empty ball containing q and its furthest Delaunay neighbor, and let b q be the
concentric ball with radius 2=3 smaller than f p . By construction, each ball b q has radius at least
Finally, for any far-reaching point q, let U q be the unit-radius ball centered at q. By
Lemma 2.5, the Swiss cheese
b q has surface area O( 3 =r), and by Lemma 2.6, each
unit ball U q
contains
(1) surface area of C. Since these unit balls are disjoint, there are at most
O( 3 =r) of them.
Nice Point Sets Can Have Nasty Delaunay Triangulations 9
Corollary 2.9. Let S be a set of points in IR 3 with spread . The Delaunay triangulation of S has
complexity O( 4 ).
Proof: For all r, let F(r) be the number of far-reaching points in S, i.e., those with Delaunay edges
of length at least r. From Theorem 2.8, we have =r). By Theorem 2.7, if the farthest
neighbor of a point p is at distance between r and r neighbors.
Thus, the total number of Delaunay edges is at most
O(r)
2.3 Conjectured Upper Bounds
We conjecture that the lower bounds in Theorem 2.4 are tight, but Corollary 2.9 is the best upper
bound known. Nearly matching upper bounds could be derived from the following conjecture,
using a divide and conquer argument suggested by Edgar Ramos (personal communication).
Let S be a well-separated set of points with closest pair distance 1, lying in two balls of radius
that are separated by distance at least c for some constant c > 1. Call an edge in the Delaunay
triangulation of S a crossing edge if it has one endpoint in each ball.
Conjecture 2.10. Some point in S is an endpoint of O() crossing edges.
Lemma 2.11. Conjecture 2.10 implies that S has O(minf 3 ; n;n 2 g) crossing edges.
Proof: Theorem 2.8 implies that only O( 2 ) points can be endpoints of crossing edges. Thus, we
can assume without loss of generality that We compute the total number of crossing
edges by iteratively removing the point with the fewest crossing edges and retriangulating the
resulting hole, say by incremental
ipping [27]. Conjecture 2.10 implies that we delete only O()
crossing edges with each point, so altogether we delete crossing edges. Not all of
these edges are in the original Delaunay triangulation, but that only helps us.
Theorem 2.12. Conjecture 2.10 implies that the Delaunay triangulation of n points in IR 3 with
spread  has complexity O(minf 3 log ; n;n 2 g).
Proof: Assume Conjecture 2.10 is true, and let S be an arbitrary set of n points with diameter ,
where the closest pair of points is at unit distance. S is contained in an axis-parallel cube C of
width . We construct a well-separated pair decomposition of S [13], based on a simple octtree
decomposition of C. The octtree has O(log ) levels. At each level i, there are 8 i cells, each a cube
of width =2 i . Our well-separated pair decomposition includes, for each level i, the points in any
pair of level-i cells separated by a distance between c=2 i and 2c=2 i . A simple packing argument
implies that any cell in the octtree is paired with O(1) other cells, all at the same level, and so
any point appears in O(log ) subset pairs. Every Delaunay edge of S is a crossing edge for some
well-separated pair of cells.
Lemma 2.11 implies that the points in any well-separated pair of level-i cells have O( 3
crossing Delaunay edges. Since there are O(8 i ) such pairs, the total number of crossing edges
between level-i cells is O( 3 ). Thus, there are O( 3 log ) Delaunay edges altogether.
Lemma 2.11 also implies that for any well-separated pair of level-i cells, the average number of
crossing edges per point is O(=2 i ). Since every point belongs to a constant number of subset pairs
at each level, the total number of crossing edges at level i is O(n=2 i ). Thus, the total number of
Delaunay edges is O(n).
This upper bound is still a logarithmic factor away from our lower bound construction when
n). However, our argument is quite conservative; all crossing edges for a well-separated
pair of subsets are counted, even though some or all of these edges may be blocked by other points
in S. A more careful analysis would probably eliminate the nal logarithmic factor.
3 Nice Surface Data
Let  be a smooth surface without boundary in IR 3 . The medial axis of  is the closure of the set
of points in IR 3 that have more than one nearest neighbor on . The local feature size of a surface
point x, denoted lfs(x), is the distance from x to the medial axis of . Let S be a set of sample
points on . Following Amenta and Bern [1], we say that S is an "-sample of  if the distance
from any point x 2  to the nearest sample point is at most "  lfs(x).
The rst step in several surface reconstruction algorithms is to construct the Delaunay triangulation
or Voronoi diagram of the sample points. Edelsbrunner and Mucke [26] and Bajaj et al.
[7, 9] describe algorithms based on alpha shapes, which are subcomplexes of the Delaunay tri-
angulation; see also [34]. Extending earlier work on planar curve reconstruction [2, 32], Amenta
and Bern [1, 3] developed an algorithm to extract a certain manifold subcomplex of the Delaunay
triangulation, called the crust. Amenta et al. [4] simplied the crust algorithm and proved that if S
is an "-sample of a smooth surface , for some su-ciently small ", then the crust is homeomorphic
to . Boissonnat and Cazals [12] and Hiyoshi and Sugihara [35] proposed algorithms to produce
a smooth surface using natural coordinates, which are dened and computed using the Voronoi
diagram of the sample points. Further examples can be found in [5, 6, 11, 16, 21].
We have already seen that even very regular "-samples of smooth surfaces can have super-linear
Delaunay complexity. In this section, we show that "-samples of smooth surfaces can have Delaunay
triangulations of quadratic complexity, implying that all these surface reconstruction algorithms
take at least quadratic time in the worst case.
3.1
We will analyze our lower bound constructions in terms of the sample measure of a smooth
surface , which we dene as follows:
Z
dx
Intuitively, the sample measure of a surface describes the intrinsic di-culty of sampling that surface
for reconstruction. 2 The next lemma formalizes this intuition.
Lemma 3.1. For any C 2 surface  and and " < 1=5, every "-sample of
contains
points.
2 Ruppert and Seidel [39] use precisely this function|but with a dierent denition of local feature size|to
measure the minimum number of triangles with bounded aspect ratio required to mesh a planar straight-line graph.
Nice Point Sets Can Have Nasty Delaunay Triangulations 11
Proof: Let S be an arbitrary "-sample of  for some " < 1=5, and let
Amenta and Bern [1, Lemma 1] observe that the local feature size function is 1-Lipschitz, that
is, jlfs(x) - lfs(y)j < jxyj for any surface points x; y 2 . Thus, for any point x 2 , we have
1-" lfs(p), where p 2 S is the sample point closest to x.
It follows that we can cover  with spheres of radius "
1-" lfs(p) around each sample point p.
Call the intersection of  and the sphere around p the neighborhood of p, denoted N(p). Similar
Lipschitz arguments imply that
for any point x 2 N(p).
For any x 2 , let n x denote the normal vector to  at x. Using the fact that local feature size
is at most the minimum radius of principal curvature, Amenta and Bern [1, Lemma 2] prove that
for any x; y 2  where
1-3- . Thus,
It follow that N(p) is monotone with respect to n p , so we can compute its
area by projecting it onto a plane normal to n p . Since the projection ts inside a circle of radius
1-" lfs(p), we have
1-" lfs(p)
min
cos \n x n p
1-" lfs(p)
We can now bound the sample measure of each neighborhood as follows: 3
min
1-" lfs(p)
1-2"
1-" lfs(p)
50
Finally, since  is covered by n such neighborhoods,
We say that an "-sample is parsimonious if it contains O(()=" 2 ) points, that is, only a
constant factor more than the minimum possible number required by Lemma 3.1.
3.2 Oversampling Is Bad
The easiest method to produce a surface sample with high Delaunay complexity is oversampling,
where some region of the surface contains many more points than necessary. In fact, the only
surface where oversampling cannot produce a quadratic-complexity Delaunay triangulation is the
sphere, even if we only consider parsimonious samples.
The idea behind our construction is to nd two skew (i.e., not coplanar) lines tangent to the
place points on these lines in small neighborhoods of the tangent points to create a complete
bipartite Delaunay graph, and then perturb the points onto the surface. The neighborhoods must
be su-ciently small that the perturbation does not change the Delaunay structure. Also, the
original tangent lines must be positioned so that the resulting Delaunay circumspheres are small,

Figure

6. Parsimoniously oversampling a non-spherical surface.
so that we can uniformly sample the rest of the surface without destroying the local quadratic
structure. See Figure 6.
To quantify our construction, we rst establish a technical lemma about perturbations. Let
be sets of m  4 evenly spaced points on two skew
lines ' P and ' Q . Every segment p i q j is an edge in the Delaunay triangulation of P [ Q. An r-
perturbation of P [ Q is a set ~
such that jp i ~
arguments imply that if r is su-ciently small, the
Delaunay triangulation of ~ P [ ~
Q also has quadratic complexity.
Let - denote the distance between successive points in both P and Q. For each point
and q j 2 Q, let  ij denote the empty ball whose boundary is tangent to ' P at p i and tangent to
' Q at q j , and let  denote the largest radius of any bitangent sphere  ij .
Lemma 3.2. Let ~
Q be an arbitrary r-perturbation of P [ Q, where r < - 2 =9. Every pair of
points ~
lies on an empty sphere with radius at most 2 and thus are neighbors in the
Delaunay triangulation of ~ P [ ~
Q.
4, we observe that  > -. The distance between any point p i to any bitangent
sphere  kj with k 6= i is at least
be the ball concentric with  ij
with radius - 2 =9 larger than  ij . This ball contains ~ p i and ~
q j but excludes every other point in
~
Q, and thus contains an empty circumsphere of ~
with radius at most  2.
Theorem 3.3. For any non-spherical C 2 surface  and any " > 0, there is a parsimonious "-sample
of  whose Delaunay triangulation has
complexity
is the number of sample points.
Proof: Let S be any parsimonious "-sample of , and let  be a sphere, centered at a
point x 2 , with radius  < lfs(x)=36m 2 , such that every point in S has distance at least 6 from
, and the intersection curve
\ is not planar (i.e., not a circle). Such a sphere always exists
unless  is itself a sphere; for example, we could take x to be any point whose principal curvatures
are dierent.
Let ' p and ' q be skew lines tangent to
at points p and q, respectively; these lines must exist
since
does not lie in a plane. Let qm be sets of evenly
spaced points on ' p and ' q , respectively, in su-ciently small neighborhoods of p and q that every
bitangent sphere  ij (see above) has radius less than 2. Such neighborhoods exist by continuity
3 We can obtain slightly better constants using the fact that every surface point lies in the neighborhood of its
closest sample point; see [1, Lemma 3].
Nice Point Sets Can Have Nasty Delaunay Triangulations 13
arguments. Let - denote the distance between successive points in P and Q and assume without
loss of generality that m- < =2. Finally, dene ~
qm g   where
~
are the surface points closest to p i and q j , respectively.
Without loss of generality, P
lies in a ball ~  of radius 2 centered at x. Lipschitz
arguments imply that  \ ~  lies between two balls of radius tangent to  at p (or
at q). Thus, any point in P (or in Q) has distance at most
R <
from , since  < lfs(x)=36m 2 . Lemma 3.2 now implies that for all i; j, there is a ball of radius less
than 4 that contains ~
excludes every other point in ~
Q. Since every other point
in S has distance at least 6 away from , this ball also excludes every point in S.
We conclude that S [ ~
Q is a parsimonious "-sample of  consisting of points whose
Delaunay triangulation has
complexity
The reconstruction algorithm of Amenta et al. [4] extracts a surface from a subset of the
Delaunay triangles of the sample points. Their algorithm estimates the surface normal at each
sample point p using the Voronoi diagram of the samples. The cocone at p is the complement of
a very wide double cone whose apex is p and whose axis is the estimated normal vector at p. The
algorithm extracts the Delaunay triangles whose dual Delaunay edges intersect the cocones of all
three of its vertices, and then extracts a manifold surface from those cocone triangles. Usually only
a small subset of the Delaunay triangles pass this ltering phase, but our construction shows that
there
are
triangles in the worst case.
3.3 Uniform Sampling Can Still Be Bad
Unfortunately, oversampling is not the only way to obtain quadratic Delaunay triangulations. Let
S be a set of sample points on the surface . We say that S is a uniform "-sample of  if the
distance form any point x 2  to its second-closest sample point is between ("=c) lfs(x) and " lfs(x),
for some constant c > 2. 4 We easily verify that a uniform "-sample is in fact an "-sample. A packing
argument similar to the proof of Lemma 3.1 implies that uniform "-samples are parsimonious.
Lemma 3.4. For any n and " >
1=n, there is a two-component surface  and an n-point uniform
"-sample S of , such that the Delaunay triangulation of S has
complexity
Proof: The surface  is the boundary of two sausages  x and  y , each of which is the Minkowski
sum of a unit sphere and a line segment. Specically, let
where U is the unit ball centered at the origin, 4n". The local feature
size of every point on  is 1, so any uniform "-sample of  has ((w
Equivalently, following Dey et al. [22], we could dene an "-sample to be uniform if jpqj= lfs(p)  "=c for any
sample points p and q, for some constant c > 1.
14 Je Erickson
Dene the seams  x and  y as the maximal line segments in each sausage closest to the xy-plane:
d) and
Our uniform "-sample S contains 2w=" along each seam:
d) for all integers -w="  i  w="; and
The Delaunay triangulation of these points has complexity (w 2 =" 2
be the ball whose boundary passes through p i and q j and is tangent to both seams.
The intersection  x \ ij is a small oval, tangent to  x at p i and symmetric about the plane

Figure

7(a).
PSfrag replacements
x
a
PSfrag replacements
a
(a) (b)

Figure

7. (a) Two sausages and a sphere tangent to both seams. (b) Computing the width of the intersection oval.
We claim that this oval lies in a su-ciently thin strip around the seam of  x that we can
avoid it with the other sample points in S. We compute the width of the oval by considering the
intersection of  x and  ij with the plane calculations imply that  ij is centered
at the point 1). The width of the intersection
oval,measured along the surface of  x , is exactly 2\p i a From Figure 7(b), we see that
tan \p i a
j"
Thus, we can bound the width of the oval as follows:
4dj"
8w
Nice Point Sets Can Have Nasty Delaunay Triangulations 15
We conclude that  x lies entirely within a strip of width less than 2" centered along the
seam  x . A symmetric argument gives the analogous result for  y \ ij . We can uniformly sample
so that no sample point lies within either strip except the points we have already placed along
the seams. Each segment p i q j is an edge in the Delaunay triangulation of the sample, and there
are
(w
Theorem 3.5. For any n and any " >
1=n, there is a connected surface  and an n-point uniform
"-sample S of , such that the Delaunay triangulation of S has
complexity
Proof: Intuitively, we produce the surface  by pushing two sausages into a spherical balloon.
These sausages create a pair of conical wedges inside the balloon whose seams lie along two skew
lines. The local feature size is small near the seams and drops quickly elsewhere, so a large fraction
of the points in any uniform sample must lie near the seams. We construct a particular sample
with points exactly along the seams that form a quadratic-complexity triangulation, similarly to
our earlier sausage construction. Our construction relies on several parameters: the radius R of the
spherical balloon, the width w and height h of the wedges, and the distance d between the seams.

Figure

8. A smooth surface with a bad uniform "-sample, and a closeup of one of its wedges.
Each wedge is the Minkowski sum of a unit sphere, a right circular cone with height h centered
along the z-axis, and a line segment of length w parallel to one of the other coordinate axes. A
wedge can be decomposed into cylindrical, spherical, conical, and planar facets. The cylindrical and
spherical facets constitute the blade of the wedge, and the seam of the blade is the line segment
of length w that bisects the cylindrical facet. The local feature size of any point on the blade is
exactly 1, and the local feature size of any other wedge point is 1 plus its distance from the blade.
Straightforward calculations imply that the sample measure of each wedge is O(w
A rst approximation e  of the surface  is obtained by removing two wedges from a ball of
radius R centered at the origin. One wedge points into the ball from below; its seam is parallel to
the x-axis and is centered at the point (0; h). The other wedge points into the ball from
above; its seam is parallel to the y-axis and is centered at (0; 0; R-h). Let
the distance between the wedges. Our construction has 1  w  d  h, so R < 3h.
To obtain the nal smooth surface , we round o the sharp edges by rolling a ball of radius
h=4 inside e
along the wedge/balloon intersection curves. We call the resulting warped toroidal
patches the sleeves. The local feature size of any point on the sleeves or on the balloon is at least
h=4. The surface area of the sleeves is O(R 2 so the sleeves have constant sample measure.
The local feature size of other surface points changes only far from the blades and by only a small
constant factor. Thus, 1). To complete the construction, we set
Figure 8.
Finally, we construct a uniform "-sample S with (w=") sample points evenly spaced along each
seam and every other point at least " away from the seams. Setting h > 5d (and thus R > 10d)
ensures that the Delaunay spheres  ij between seam points do not touch  except on the blades.
By the argument in Lemma 3.4, there
are
(w
points.
3.4 Some Surfaces Are Just Evil
In this section, we describe a family of surfaces for which any parsimonious "-sample has a Delaunay
triangulation of near-quadratic complexity. First we give a nearly trivial construction of a bad
surface with several components, and then we join these components into a single connected surface
using a method similar to Theorem 3.5.
Lemma 3.6. For any n and any " >
1=n, there is a smooth surface  such that the Delaunay
triangulation of any parsimonious "-sample of  has
complexity
is the size of
the sample.
Proof: Let P be a set containing the following k points:
We easily verify that every pair of points p i and q j lie on the boundary of a ball  ij with every
other point in P at least unit distance outside. (See Lemma 3.2.)
is the unit-radius sphere centered at p. Clearly,
for every point x 2 , so be an arbitrary parsimonious "-sample of , let
be the sample points on its unit
sphere.
Choose an arbitrary pair P. By construction,  ij contains only points in S p i
and S q j
its center until (without loss of generality) it has no points of S p i
in its interior.
Choose some point
on the boundary of the shrunken ball, and then shrink the ball
further about p 0 until it contains no point of S q i
. The resulting ball has p 0 and some q 0 2 S q i
on
its boundary, and no points of S in its interior. Thus, p 0 and q 0 are neighbors in the Delaunay
triangulation of S. There are at
least
To create a connected surface where good sample has a complicated Delaunay triangulation,
we add 'teeth' to our earlier balloon and wedge construction. Unfortunately, in the process, we
lose a polylogarithmic factor in the Delaunay complexity.
Theorem 3.7. For any n and any " <
1=n, there is a smooth connected surface  such that
the Delaunay triangulation of any parsimonious "-sample of  has
complexity
where n is the size of the sample.
Nice Point Sets Can Have Nasty Delaunay Triangulations 17
Proof: As in Theorem 3.5, our surface  contains two wedges, but now each wedge has a row of small
conical teeth. Our construction relies on the same parameters R; w;h of our earlier construction.
We now have additional parameter t, which is simultaneously the height of the teeth, the distance
between the teeth, and half the thickness of the 'blade' of the wedge.
Our construction starts with the (toothless) surface described in the proof of Theorem 3.5, but
using a ball of radius t instead of a unit ball to dene the wedges. We add w=t evenly-spaced teeth
along the blade of each wedge, where each tooth is the Minkowski sum of a unit ball with a right
circular cone of radius t. Each tooth is tangent to both planar facets of its wedge. To create the
nal smooth surface , we roll a ball of radius t=3 over the blade/tooth intersection curves. The
complete surface has sample measure ((w=t)(1+log t)+log h 1). Finally, we set the parameters
Let S be a parsimonious "-sample of , and let any pair of teeth,
one on each wedge, there is a sphere tangent to the ends of the teeth that has
distance
(1) from
the rest of the surface. We can expand this sphere so that it passes through one point on each
tooth and excludes the rest of the points. Thus, the Delaunay triangulation of S has complexity
3.5 Randomness Doesn't Help Much
Golin and Na [33] proved that if S is a random set of n points on the surface of a convex polytope
with a constant number of facets, then the expected complexity of the Delaunay triangulation of S
is O(n). Unfortunately, this result does not extend to nonconvex objects, even when the random
distribution of the points is proportional to the sample measure.
Theorem 3.8. For any n, there is a smooth connected surface , such that the Delaunay triangulation
of n independent uniformly-distributed random points in  has complexity (n
with high probability.
Proof: Consider the surface  consisting of (n= log n) unit balls evenly spaced along two skew line
segments, exactly as in the proof of Theorem 3.6, with extremely thin cylinders joining them into
a single connected surface resembling a string of beads. With high probability, a random sample
of n points contains at least one point on each ball, on the side facing the opposite segment. Thus,
with high probability, there is at least one Delaunay edge between any ball on one segment and
any ball on the other segment.
Theorem 3.9. For any n, there is a smooth connected surface , such that the Delaunay triangulation
of n independent random points in , distributed proportionally to the sample measure, has
complexity log 4 n) with high probability.
Proof: Let  be the surface used to prove Theorem 3.7, but with (n= log 2 n) teeth. With high
probability, a random sample of  contains at least one point at the tip of each tooth.
Conclusions
We have derived new upper and lower bounds on the complexity of Delaunay triangulations under
two dierent geometric constraints: point sets with sublinear spread and good samples of smooth
surfaces. Our results imply that with very strong restrictions on the inputs, most existing surface
reconstruction algorithms are ine-cient in the worst case.
Our results suggest several open problems, the most obvious of which is to tighten the spread-
based bounds. We conjecture that our lower bounds are tight. Even the special case of dense point
sets is open.
Another natural open problem is to generalize our analysis to higher dimensions. Dey et al. [22]
describe a generalization of the cocone algorithm [4] that determines the dimension of a uniformly
sampled manifold (in the sense of Section 3.3) in a space of any xed dimension. Results developed
in a companion paper [29] imply that for any n and
p n, there is a set of n points in IR d
with spread  whose Delaunay triangulation has
complexity
(n dd=2e-1 ). The techniques used in
Section 2.2 generalize easily to prove that any d-dimensional Delaunay triangulation has O( d+1 )
edges, but this implies a very weak bound on the overall complexity. We conjecture that the
complexity is always O( d )|in particular, O(n) for all dense point sets|and can only reach the
maximum
(n).
Our bad surface examples are admittedly quite contrived, since they have areas of very high
curvature relative to their diameter. An interesting open problem is whether there are bad surfaces
with smaller 'spread', i.e., ratio between diameter and minimum local feature size. What is the
worst-case complexity of the Delaunay triangulation of good surface samples as a function of the
spread and sample measure of the surface? Is there a single surface such that for any ", there is
a uniform "-sample with quadratic Delaunay complexity, or (as I conjecture) is the cylinder the
worst case? Even worse, is there a \universally bad" surface such that every uniform sample of
has super-linear Delaunay complexity?
Our surface results imply that most Delaunay-based surface reconstruction algorithms can be
forced to take super-linear time, even for very natural surface data. It may be possible to improve
these algorithms by adding a small number of Steiner points in a preprocessing phase to reduce the
complexity of the Delaunay triangulation. In most of our bad surface examples, a single Steiner
point reduces the Delaunay complexity to O(n). Bern, Eppstein, and Gilbert [10] show that any
Delaunay triangulation can be reduced to O(n) complexity in O(n log n) time by adding O(n)
Steiner points; see also [15]. Unfortunately, the Steiner points they choose (the vertices of an
octtree) may make reconstruction impossible. In order to be usable, any new Steiner points must
either lie very close to or very far from the surface, and as our bad examples demonstrate, both
types of Steiner points may be necessary. Boissonnat and Cazals (personal communication) report
that adding a small subset of the original Voronoi vertices as Steiner points can signicantly reduce
the complexity of the resulting Voronoi diagram with only minimal changes to the smooth surface
constructed by their algorithm [12].
After some of the results in this paper were announced, Dey et al. [20] developed a surface re-construction
algorithm that does not construct the entire Delaunay triangulation. Their algorithm
runs in O(n log n) time if the sample is locally uniform, meaning (loosely) that the density of the
sample points varies smoothly over the surface, but still requires quadratic time in the worst case.
Even more recently, Ramos [38] discovered a fast algorithm to extract a locally uniform sample
from any "-sample, thereby producing a surface reconstruction algorithm that provably runs in
O(n log n) time.
Finally, are there other natural geometric conditions under which the Delaunay triangulation
provably has small complexity?
Nice Point Sets Can Have Nasty Delaunay Triangulations 19

Acknowledgments

. I thank Herbert Edelsbrunner for asking the (still open!) question that started
this work, Kim Whittlesey for suggesting charging Delaunay features to area, Edgar Ramos for
suggesting well-separated pair decompositions, and Tamal Dey and Edgar Ramos for sending me
preliminary copies of their papers [20, 22, 38]. Thanks also to Sariel Har-Peled, Olivier Devillers,
and Jean-Daniel Boissonnat for helpful discussions.



--R

Surface reconstruction by Voronoi
The crust and the
A new Voronoi-based surface reconstruction algorithm
A simple algorithm for homeomorphic surface recon- struction
The power crust

Automatic reconstruction of surface and scalar
Realistic input models for geometric algorithms.
Sampling and reconstructing manifolds using alpha-shapes
Provably good mesh generation.
Representing 2d and 3d shapes with the Delaunay triangulation.
Smooth surface reconstruction via natural neighbour interpolation of distance functions.
A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential elds
Pattern matching for spatial point sets.
Selecting heavily covered points.
Dynamic skin triangulation.
Sliver exudation.
Nearest neighbor queries in metric spaces.
Improved bounds for planar k-sets and related problems
Surface reconstruction in almost linear time under locally uniform sampling.
Detecting undersampling in surface reconstruction.
Shape dimension from samples.
The expected number of k-faces of a Voronoi diagram



Incremental topological ipping works for regular triangulations.
Cutting dense point sets in half.
Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes
Nice point sets can have nasty Delaunay triangulations.
Geometric pattern matching: A performance study.

On the average complexity of 3d-Voronoi diagrams of random points on convex polytopes
Surface reconstruction using alpha shapes.

Geometric matching under noise: Combinatorial bounds and algorithms.
Generating sliver-free three dimensional meshes
Smooth surface reconstruction in near linear time.
A Delaunay re
Tetrahedral mesh generation by Delaunay re
An improved bound for k-sets in three dimensions
Convex independent sets and 7-holes in restricted planar point sets

Planar Point Sets with Bounded Ratios of Distances.
Approximate center points in dense point sets.
On Fatness and Fitness: Realistic Input Models for Geometric Algorithms.
--TR
Higher-dimensional Voronoi diagrams in linear expected time
Three-dimensional alpha shapes
Provably good mesh generation
Selecting Heavily Covered Points
A decomposition of multidimensional point sets with applications to <italic>k</italic>-nearest-neighbors and <italic>n</italic>-body potential fields
Automatic reconstruction of surfaces and scalar fields from 3D scans
Realistic input models for geometric algorithms
Tetrahedral mesh generation by Delaunay refinement
A new Voronoi-based surface reconstruction algorithm
The crust and the MYAMPERSANDBgr;-Skeleton
<italic>r</italic>-regular shape reconstruction from unorganized points
Sliver exudation
Crust and anti-crust
Smoothing and cleaning up slivers
A simple algorithm for homeomorphic surface reconstruction
Smooth surface reconstruction via natural neighbour interpolation of distance functions
Voronoi-based interpolation with higher continuity
Dynamic skin triangulation

--CTR
Mordecai J. Golin , Hyeon-Suk Na, The probabilistic complexity of the Voronoi diagram of points on a polyhedron, Proceedings of the eighteenth annual symposium on Computational geometry, p.209-216, June 05-07, 2002, Barcelona, Spain
Sunghee Choi , Nina Amenta, Delaunay triangulation programs on surface data, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.135-136, January 06-08, 2002, San Francisco, California
Mordecai J. Golin , Hyeon-Suk Na, On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes, Computational Geometry: Theory and Applications, v.25 n.3, p.197-231, July
Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Proceedings of the eighteenth annual symposium on Computational geometry, p.33-42, June 05-07, 2002, Barcelona, Spain
Yogish Sabharwal , Nishant Sharma , Sandeep Sen, Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions, Journal of Computer and System Sciences, v.72 n.6, p.955-977, September 2006
Sariel Har-Peled , Shakhar Smorodinsky, On conflict-free coloring of points and simple regions in the plane, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
Sunghee Choi, The Delaunay tetrahedralization from Delaunay triangulated surfaces, Proceedings of the eighteenth annual symposium on Computational geometry, p.145-150, June 05-07, 2002, Barcelona, Spain
Pankaj Agarwal , Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Computational Geometry: Theory and Applications, v.28 n.2-3, p.137-163, June 2004
Dominique Attali , Jean-Daniel Boissonnat , Andr Lieutier, Complexity of the delaunay triangulation of points on surfaces the smooth case, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
Jeff Erickson, Local polyhedra and geometric graphs, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
J. D. Boissonnat , S. Oudot, Provably good surface sampling and approximation, Proceedings of the Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
Tamal K. Dey , Joachim Giesen , Samrat Goswami , Wulue Zhao, Shape dimension and approximation from samples, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.772-780, January 06-08, 2002, San Francisco, California
Stefan Funke , Edgar A. Ramos, Smooth-surface reconstruction in near-linear time, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.781-790, January 06-08, 2002, San Francisco, California
Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos , Tathagata Ray, Sampling and meshing a surface with guaranteed topology and geometry, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
Dominique Attali , Jean-Daniel Boissonnat, A linear bound on the complexity of the delaunay triangulation of points on polyhedral surfaces, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrcken, Germany
Raphalle Chaine, A geometric convection approach of 3-D reconstruction, Proceedings of the Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
Jeff Erickson, Dense point sets have sparse Delaunay triangulations: or "but not too nasty", Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.125-134, January 06-08, 2002, San Francisco, California
delaunay triangulation;sample measure;sample;spread;lower bounds;surface reconstruction