Representing geometric structures in d dimensions: topology and order

We develop a representation for the topological structure of subdivided manifolds (with and without boundary) of dimension d ≥ 1 which allows straightforward access of the available order information. It is shown that there exists a large amount of ordering information in subdivided manifolds: given a (k-2)-cell in the boundary of a (k+1)-cell, 1 ≤ k ≤ d, all of the k- and (k-1)-cells 'between them' can be ordered 'around' the (k-2)-cell. This includes the usual orderings in 2- and 3-dimensional objects. We introduce the 'cell-tuple structure', a simple, uniform representation of the incidence and ordering information in a subdivided manifold. It includes the quad-edge data structure of Guibas and Stolfi [GS 85] and the facet-edge data structure of Dobkin and Laszlo [DL 87] as special cases in dimensions 2 and 3, respectively.