General convex hull using the gem data structure

We describe in detail a general algorithm for constructing the convex hull of a finite set of points in Euclidean space of arbitrary dimension $n$. The algorithm handles degenerate situations, such as non-simplicial faces and point sets contained in a lower-dimensional subspace. The topology of the hull is kept in a graph encoded map (gem) data structure, a novel representation for $n$-dimensional triangulations. The gem representation, which was introduced as a mathematical device by S. Lins in 1982, extends the cell-tuple (or generalized map) representation proposed by Brisson and Lienhardt to maps that are not barycentric subdivisions, to manifolds with borders, and to non-manifold (but triangulable) topological spaces.

2006