Robust gift wrapping for the three-dimensional convex hull (Q1337472)

The authors address the problem of finding the convex hull of a 3D point set using finite precision arithmetic. Existing algorithms presuppose exact arithmetic and cannot be used with confidence in floating point computations. The main idea of the procedure is to use the equivalence of polyhedra and planar graphs given by Steinitz's theorem and to use numerical data to update the graph so that it will represent a polyhedron of genus 0 at all stages. This means that instead of guaranteeing convexity, the algorithm only guarantees topological equivalence to a convex hull. In addition, the algorithm is still not unconditionally stable; some possible modifications to achieve stability in all cases are indicated.