Chapter 9: Degeneracy and Robustness

Overview

A geometric data structure for a set of geometric objects must be computed by an algorithm. An algorithm that handles geometric input and produces geometric output is called a geometric algorithm . The decisions and the output of a geometric algorithm depend on geometric predicate s and on the computation of new and intermediate geometric objects. Geometric computation has two components : a numerical part and a combinatorial part. Numerical computation is involved in both the construction of new objects and in the evaluation of geometric predicates. The combinatorial part takes care of the representation and correctness of the combinatorial structure of (sub)results.

For example, the Voronoi diagram of a set P of points in 2D is a subdivision of the plane into cells of nearest neighborship. That is, a Voronoicell of a Voronoisite p ˆˆ P is the set of all points that are closer to p than to any other point q ˆˆ P ; see Figure 9.1 for an example and Chapter 6 for a detailed discussion.

Figure 9.1: The Voronoi diagram for a set of sites subdivides the plane into regions of the nearest neighborship.

The combinatorial part of the Voronoi diagram is given by the graph of the subdivision. The exact coordinates of the vertices of the graph and the corresponding edges, which are also called Voronoi vertices and Voronoi edges , respectively, represent the numerical part of the problem. Note that other combinatorial representations of the Voronoi diagram are valid as well. For example, we can store a list of clockwise-ordered neighboring sites for every site p . This represents the structure of the Voronoi diagram without any numerical information.

Another example of a geometric problem is the computation of the convexhull of a set P of points in 2D. The convex hull of a set P is the smallest convex polygon that contains all points. We can describe the combinatorial structure of the convex hull by a circular list of successive points on the hull stemming from P ; see Figure 9.2. A numerical part is not necessary for the output; it is only necessary for the computation of this list.

Figure 9.2: The convex hull for a set of points is the smallest convex set that contains all points.

There are two difficulties for the practical implementation of many geometric algorithms. On one hand, the problem of the numerical part lies in the precision of arithmetic, which influences also the combinatorial results and the flow of an algorithm. Thus, we are looking for robustness of the underlying arithmetic.

On the other hand, for the flow of the algorithm itself, we have to study input scenarios of geometric objects that are not independent of each other. Many geometric algorithms behave well if the given objects are assumed to be in general position . For example, a set of points in the plane is in general position if no three points are colinear and no four points are cocircular. Non-general positions are also denoted as degeneracy . The influence of and how to deal with degeneracy is the subject of Section 9.5.

There are many surveying articles considering robustness issues and degeneracy in geometric computing. We will try to give an overview and use elements mainly from [Fortune 96], [Schirra 00], [Shewchuk 97], [Yap 97b], [Sugihara 00], [Goldberg 91], [Michelucci 97], [Santisteve 99], and [Mehlhorn and Nher 94], and additionally from [Guibas et al. 89, Burnikel et al. 99, Burnikel et al. 94, Fortune and Van Wyk 93, Fortune 89, Yap 97a, Sugihara and Iri 89, Sugihara et al. 00].

First, we discuss two simple examples in 2D and 3D and point out the influence of impreciseness in Section 9.1. As a side effect, we will introduce a data structure that efficiently represents the combinatorial structure of graphs in different dimensions. Later, we will turn over to the problem of degeneracy in the combinatorial flow of an algorithm; see Section 9.5.