CONSTRUCTING STRONGLY CONVEX APPROXIMATE HULLS WITH INACCURATE PRIMITIVES

The first half of this paper introduces Epsilon Geometry, a framework for the development of robust geometric algorithms using inaccurate pr imitives. Epsilon Geometry is based on a very general model of impreci se computations, which includes floating-point and rounded-integer ari thmetic as special cases. The second half of the paper introduces the notion of a (-epsilon)-convex polygon, a polygon that remains convex e ven if its vertices are all arbitrarily displaced by a distance of eps ilon of less, and proves some interesting properties of such polygons. In particular, we prove that for every point set there exists a (-eps ilon)-convex polygon H such that every point is at most 4epsilon away from H. Using the tools of Epsilon Geometry, we develop robust algorit hms for testing whether a polygon is (-epsilon)-convex, for testing wh ether a point is inside a (-epsilon)-convex polygon, and for computing a (-epsilon)-convex approximate hull for a set of points.