The implementation of an algorithm to find the convex hull of a set of three-dimensional points

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)


A detailed description of the implementation of a three-dimensional convex hull algorithm is given. The problems experienced in the production and testing of a correct and robust implementation of a geometric algorithm are discussed. Attention is paid to those issues that are often brushed over in the theoretical descriptions but cause errors in a real computation. These include degeneracies such as coplanar points, floating-point errors, and other special, but not necessarily degenerate, cases.
Original languageEnglish
Pages (from-to)105-132
Number of pages28
JournalACM Transactions on Graphics
Issue number1
Publication statusPublished - 1990

Cite this