Convex Hulls in Higher-dimensional Space

Michael Müller - Joachim Ziegler - Kurt Mehlhorn - Michael Seel

Abstract:

We define and implement the data type chull. It maintains convex hulls in arbitrary dimensions and supports insertions of points and membership queries. The interior of the hull and the boundary of the hull are simplicial complexes. Both complexes can be traversed.

An original version of this report ([MZ94]) was written by the first two authors in 94. At this point LEDA had no support for higher-dimensional geometry. A kernel for higher-dimensional geometry was designed in 95 and 96. Its design was heavily influenced by the experiences with the convex hull program. The third author adopted the program to the new kernel. The fourth author templatized the code to allow substitution of geometric objects and primitives.