Simultaneous storage of primal and dual three-dimensional subdivisions

We propose a new general-purpose data structure useful for a variety of three-dimensional applications. The data structure has the characteristic of storing simultaneously the primal and dual subdivisions of a three-dimensional manifold. We argue in this paper that storing both subdivisions, for instance the Voronoi diagram and the Delaunay tetrahedralization, can be beneficial for many application domains, notably for the modelling of datasets in geosciences or for representing boundaries of real-world features. Our structure is an extension of the well-known quad-edge data structure used for representing two-dimensional manifolds. We describe the basic properties of this augmented quad-edge structure, along with the navigation operators, and we also demonstrate its usefulness with some examples of applications.