Exact and optimal convex hulls in 2D

Citation
H. Ratschek et J. Rokne, Exact and optimal convex hulls in 2D, INT J C GEO, 10(2), 2000, pp. 109-129
Citations number
30
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
ISSN journal
02181959 → ACNP
Volume
10
Issue
2
Year of publication
2000
Pages
109 - 129
Database
ISI
SICI code
0218-1959(200004)10:2<109:EAOCHI>2.0.ZU;2-G
Abstract
We present an algorithm for computing the convex hull of a finite set of po ints. The algorithm is based on a version of Graham scan with the following additional features: If the points are already (single precision) machine numbers, the computati on is rounding-error free, that is, the computed hull is the hull that woul d have been computed if real arithmetic was available. If the points are arbitrary numbers, the algorithm renders the smallest pos sible machine representable convex hull that includes the exact convex hull . The computation time is still O(n log(2) n). Only floating point arithmetic with double mantissa length is required. No mantissa splitting or other mantissa manipulations are needed; one only has to know the exponent parts of the numbers. Also, no fixed point accumulato r is needed. Single precision interval arithmetic is recommended for accelerating the co mputation, but is not necessary. All of these aims are achieved with a new method for exact determination of the sign of a sum.