Robust gift wrapping for the three-dimensional convex hull

✍ Scribed by Kokichi Sugihara

• Book ID: 104147824
• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 893 KB
• Volume: 49
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(05)80056-x

✦ Synopsis

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-priority 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.