Title

Deriving an optimal algorithm for red/blue segment intersection by degree-driven design of geometric algorithms

Abstract

It has always bothered me that geometric algorithms that we prove are correct can still fail due to numerical precision issues.  This is because we prove them correct for a model of computation that supports operation on real numbers, but we implement them on computers that use floating point.

Liotta, Preparata and Tamassia suggested that considerations of precision could be incorporated into the design of geometric algorithms by limiting the degree of polynomials used to compute predicates.  For example, for testing if two line segments cross at an intersection point, degree 2 (so roughly double precision) is enough, since you simply test if each segment's endpoints are on opposite sides of the line through the other segment. The coordinates of an intersection are rational polynomials of degree 3 over degree 2, however, so comparing the x-coordinates of intersections is a degree-5 operation (roughly 5 times input precision).  This is why the classic Bentley-Ottmann sweep, which finds all k intersections of n line segments in O((n+k) log n) time, has numerical problems. 

For the special case of red/blue segment intersection, in which there are no red/red or blue/blue crossings (cases occur in CAD/CAM computing intersections or unions of two polygonal regions, or in GIS overlaying two maps), Andrea Mantler and I derived a degree 2 algorithm that runs in O(n log n + k) time several years ago.  Recently I've simplified and extended this algorithm as an example of how degree driven design can lead to correct geometric algorithms that handle all degenerate inputs in a consistent way; it is the basis of a series of programming assignments for an undergraduate algorithms class.  I'll describe the algorithm and comment on what I and the students are learning through this assignment.