Contents
10 Geometry Algorithms page 2
10.1 Convex Hulls 2
10.2 Triangulations 21
10.3 Verification of Geometric Structures, Basics 29
10.4 Delaunay Triangulations and Diagrams 37
10.5 Voronoi Diagrams 51
10.6 Point Sets and Dynamic Delaunay Triangulations 73
10.7 Line Segment Intersection 96
10.8 Polygons 123
10.9 A Glimpse at Higher-Dimensional Geometric Algorithms 155
10.10 A Complete Program: The Voronoi Demo 160
Bibliography 178
Index 180
1
10
Geometry Algorithms
We discuss convex hulls, triangulations, the verification of geometric structures, Delaunay
triangulations and Delaunay diagrams, Voronoi diagrams, applications of Delaunay and
Voronoi diagrams, geometric dictionaries, line segment intersection, polygons, and close
with a glimpse at higher-dimensional computation geometry. For each problem we in-
troduce the required mathematics and derive algorithms and their implementations. The
books [Meh84b, Ede87, PS85, Mul94, Kle97, BY98, dBKOS97] provide a wider view of
computational geometry.
The chapter uses results of all preceding chapters and is, in this sense, the culmination
point of the book, e.g., we use lists and arrays from the basic data types, integers and
rationals from the number types, dictionaries, maps and sorted sequences from the advanced
data types, graphs and graph algorithms, embedded graphs, and the geometry kernels.
Computational geometry is a very rich area and LEDA certainly does not provide every-
thing there is to it. Other good sources of geometric software are CGAL [CGA] and the
LEDA extension packages [LEP].
10.1 Convex Hulls
The convex hull problem in the plane is one of the simplest geometric problems and hence
a good starting point for our exploration of geometry algorithms. It will allow us to address
five important themes in a simple setting:
• The sweep paradigm: In this paradigm the input points are first sorted according to the
lexicographic order and then the desired geometric structure is constructed
incrementally during a single sweep over the points. We will derive and implement a
2
10.1 Convex Hulls 3
Figure 10.1 A convex and a non-convex set.
Figure 10.2 A point set, its convex hull, and its width. The figure was generated with the
xlman-demo voronoi
demo. The width of point sets is discussed in Section 10.1.3.
sweep algorithm for convex hulls. We will see more applications of the sweep
paradigm in later sections.
• The (randomized) incremental construction paradigm: In this paradigm the input
points are considered one by one in either arbitrary or random order and the desired
geometric structure is constructed incrementally. We will derive and implement an
incremental algorithm for convex hulls.
• The careful handling of degeneracies: The literature on computational geometry
frequently makes the so-called general position assumption which states that only
inputs are considered for which none of the geometric predicates required by the
algorithm (recall that the evaluation of a geometric predicate calls for the evaluation of
the sign of an expression) ever evaluates to zero. For example, the incremental
4 Geometry Algorithms
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
p
v
0
v
2
v
3
w
0
w
1
v
1
Figure 10.3 Two point sets and their convex hulls. The hulls are represented as cyclic lists of
points, namely v
0
,v
1
,v
2
,v
3
for the example on the left and w
0
,w
1
for the example on the right.
algorithm for convex hulls uses the orientation predicate and hence the general
position assumption excludes all inputs containing three collinear points. Of course,
we do not want to exclude any inputs and hence cannot make the general position
assumption. Dropping the general position assumption typically requires a more
careful formulation of the algorithms. The sweep as well as the incremental algorithm
for convex hulls will work for all inputs. In fact, all algorithms in this chapter do.
• Verification of geometric structures: Geometric programs require checking. Although
the convex hull problem is one of the simplest geometric problems, the programs
derived in this section will be non-trivial. We will see how to partially check the output
of convex hull programs in Section 10.3.
• The importance of exact geometric primitives: In the preceding chapter we introduced
the rational geometry kernel; in this section we will profit from it.
A set C is called convex if for any two points p and q in C the entire line segment pq is
contained in C, see Figure 10.1. The convex hull conv S of a set S of points is the smallest
(with respect to set inclusion) convex set containing S. A point p ∈ S is called an extreme
point of S if there is a closed halfspace containing S such that p is the only point in S that
lies in the boundary of the halfspace. A point p ∈ S is called a weak extreme point of S if
there is a closed halfspace containing S such that p lies in the boundary of the halfspace.
Clearly, an extreme point is also a weak extreme point, but there may be weak extreme
points that are not extreme points. The point p in Figure 10.3 is an example.
From now on we restrict our discussion to the plane. If S contains no three collinear
points then every weak extreme point is also extreme, i.e., under the general position as-
sumption there is no need to distinguish between weak extreme points and extreme points.
We define the convex hull problem as the problem of computing the extreme points of a
finite set of points as a cyclically ordered list of point, see Figure 10.3. The cyclic order is
the clockwise order in which the extreme points appear on the hull.
10.1 Convex Hulls 5
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
p
q
Figure 10.4 Adding point p. We determine the two tangents from p by a clockwise and
counter-clockwise walk along the current hull starting at the most recently added point q.
The function
list<POINT> CONVEX HULL(const list<POINT>& L);
computes the convex hull of the points in L and returns its list of vertices. The cyclic order
of the vertices in the result corresponds to the clockwise order of the vertices on the hull.
The algorithm uses randomized incremental construction and its expected running time is
O(n log n).
10.1.1 The Sweep Algorithm
The sweep algorithm for convex hulls consists of the following three steps:
• The input points are sorted in increasing lexicographic order.
• The convex hull is initialized with the two lexicographically smallest points in L.
• The remaining points are considered in increasing lexicographic order and the convex
hull is updated for each point. Assume that p is the next point to be considered and
that we have already constructed the convex hull of the preceding points. The new hull
can be obtained from the old hull by constructing the two tangents from p. The
construction of the tangents is simple since p is guaranteed to see the point q added
just before p. We only have to walk from q in clockwise and counter-clockwise
direction along the hull in order to determine the other endpoints of the tangents, see
Figure 10.4.
We now turn this strategy into a program. We assume that the set S is given as a list L0 of
points. We allow multiple occurrences of points. We follow the general outline above and
proceed in three steps. We first make a local copy L of L0 and sort L. Next we initialize
the list of hull vertices with the first two points (in the sorted version) of L, and finally, we
add all other points of L. We call the resulting program CONVEX
HULL S since it uses
the sweep paradigm to compute convex hulls.
