EXACT AND OPTIMAL CONVEX HULLS IN 2D
Helmut Ratschek, Jon George Rokne · International Journal of Computational Geometry & Applications · 2000
We present an algorithm for computing the convex hull of a finite set of points. 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 computation is rounding-error free, that is, the computed hull is the hull that would have been computed if real arithmetic was available. • If the points are arbitrary numbers, the algorithm renders the smallest possible 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 accumulator is needed. • Single precision interval arithmetic is recommended for accelerating the computation, but is not necessary. • All of these aims are achieved with a new method for exact determination of the sign of a sum.