Exact and optimal convex hulls in 2D

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.