Epsilon geometry: building robust algorithms from imprecise computations

Abstract

This thesis introduces Epsilon Geometry, a framework for the development of robust geometric algorithms using inaccurate primitives. Epsilon Geometry is based on a very general model of imprecise computations, which includes floating-point and rounded-integer arithmetic as special cases. The algorithms in this framework produce exact solutions for perturbed versions of their input and return a bound on the size of these implicit perturbations. The thesis begins with a formal description of the Epsilon Geometry framework. It introduces the notions of an epsilon predicate, a geometric predicate that can be satisfied by a perturbed version of its arguments; and a critical distance, the size of the perturbation required to make an epsilon predicate true. It also introduces epsilon and delta boxes, the implementations of these mathematical concepts as computer programs. The thesis describes some general rules for turning mathematical lemmas about epsilon predicates and critical distances into implementations of epsilon and delta boxes. Next, it presents a basic set of two-dimensional geometric predicates that are used for all of the algorithms in the sequel. The second half of the thesis examines how Epsilon Geometry can be applied to various geometric objects and algorithms in the plane. It defines the notions of an $\varepsilon$-convex polygon, a polygon that can be made convex by perturbing each of its vertices by $\varepsilon$ or less; and a ($-\varepsilon)$-convex polygon, a polygon that remains convex even if its vertices are all displaced in arbitrary directions by a distance of $\varepsilon$ or less. The thesis develops robust algorithms for testing point inclusion in both kinds of polygons, and for testing a polygon's degree of convexity. Finally, the thesis investigates the existence of approximate hulls for sets of points. It proves that for every point set there exists a ($-\varepsilon$)-convex polygon H such that every point of the set is at most 4$\varepsilon$ away from H, and it describes robust algorithms for computing such hulls.