Robust geometric computation

(Extremely rough draft #1)

Introduction

Geometric objects on a digital computer are composed of two types of data: numerical and combinatorial. Examples of numerical data include the Cartesian coordinates of a point in 3-space, the length of a line segment connecting two such points, or the angle between two such line segments. Examples of combinatorial information include grouping two points as an edge, grouping a collection of edges as a face, or grouping a collection of faces as a surface.

Geometric algorithms that operate on geometric objects are best thought of as two types of operations: predicates and constructions. Predicates determine relationships between objects. A predicate might determine if a point is to the left, right, or is collinear with a line segment, determine if a point is inside, outside, or on a circle, or determine if a line intersects a plane in one, none, or infinitely many points. Constructions produce new geometric objects from existing geometric objects. A construction might produce the rotation of a point around an origin, produce the point of intersection between two line segments, or produce an offset of an algebraic curve.

Geometric algorithms are typically designed and analyzed using the Real-RAM model of computation. In other words, these algorithms assume that the numerical data in geometric objects are exact values in $\mathbb {R}$ that can be stored and retrieved in constant time, and that arithmetic involving these values is performed in constant time. From a practical point of view, it may seem like an odd or frustrating decision to assume access to infinite precision real arithmetic, given that digital computers are finite objects. From a theoretical point of view, this is a sensible choice given that for subsets of $\mathbb {R}$, such as the rational numbers $\mathbb {Q}$, many fundamental geometric axioms no longer hold.

Geometric nonrobustness results from this unfortunate disconnect between continuous theoretical formulations and the reality of discrete machine implementation. In most instances, the numerical data composing geometric objects is an approximation to a real value. Predicates that assume exact values but are fed approximate values are liable to make incorrect determinations. Constructions compound the situation by taking exact values and producing approximate ones, or by taking approximate values and producing even coarser approximations. In short, geometric nonrobustness is a problem wherein branching decisions in geometric algorithms are predicated on approximate numerical computations, leading to various forms of unreliability including ill-formed output and software failure through crashing or infinite loops.

Section 3

blah blah

Section 4

blah blah blah