Gems: A general data structure for $d$-dimensional triangulations

We describe in detail a novel data structure for $d$-dimensional triangulations. In an arbitrary $d$-dimension triangulation, there are $d!$ ways in which a specific facet of an simplex can be glued to a specific facet of another simplex. Therefore, in data structures for general $d$-dimensional triangulations, this information must be encoded using $\lceil \log_2(d!) \rceil$ bits for each adjacent pair of simplices. We study a special class of triangulations, called the \emph{colored triangulations}, in which there is a only one way two simplices can share a specific facet. The \emph{gem data structure}, described here, makes use of this fact to greatly simplify the repertoire of elementary topological operators.

2006