Robust gift wrapping for the three-dimensional convex hull

摘要

A conventional gift-wrapping algorithm for constructing the three-dimensional convex hull is revised into a numerically robust one. The proposed algorithm places the highest priority on the topological condition that the boundary of the convex hull should be isomorphic to a sphere, and uses numerical values as lower-prirority information for choosing one among the combinatorially consistent branches. No matter how poor the arithmetic precision may be, the algorithm carries out its task and gives as the output a topologically consistent approximation to the true convex hull.