A Data Structure for Manipulating Three-Dimensional Subdivisions (thesis)

Abstract:

A major impediment to the implementation of algorithms that manipulate 3-dimensional cell complexes and subdivisions is the non-existence of a suitable data structure. What is needed is a data structure which is powerful enough to model such objects while being simple enough to allow their manipulation in
well defined ways. We focus attention here on the development of such data structure. Our structure is analogous (though one dimension higher) to Baumgart's winged-edge and Guibas and Stolfi's quad-edge data structures which are widely accepted for modelling 2-manifolds. Just as these structures can be
used to represent both planar polygonal cell complexes in R3 and surfaces of 4-polyhedra, our results can be viewed as similar to the work done by Guibas and Stolfi in deriving the quad-edge structure, one dimension higher. (Note: paper has been copied with two pages per sheet)