ISSN:
1432-0541
Keywords:
Computational geometry
;
Epsilon Geometry
;
Approximate computations
;
Robust algorithms
;
Strongly convex polygons
;
Convex hull
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The first half of this paper introducesEpsilon 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 second half of the paper introduces the notion of a (−ɛ)-convex polygon, a polygon that remains convex even if its vertices are all arbitrarily displaced by a distance ofɛ of less, and proves some interesting properties of such polygons. In particular, we prove that for every point set there exists a (−ɛ)-convex polygonH such that every point is at most 4ɛ away fromH. Using the tools of Epsilon Geometry, we develop robust algorithms for testing whether a polygon is (−ɛ)-convex, for testing whether a point is inside a (−ɛ)-convex polygon, and for computing a (−ɛ)-convex approximate hull for a set of points.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01190154
Permalink
