Constructing the 3D Voronoi Diagram from a 3D Delaunay Tessallation

Question

I'm trying to convert a 3D Delaunay Tessallation (generated with TetGen) to a Voronoi Diagram. I know TetGen can create Voronoi Diagrams, but I need to perform the conversion myself due to unusual boundary conditions.

I'm totally stumped with the duality here. I have two of the four:

1. Each Delaunay vertex corresponds to one Voronoi cell (the center of the cell is at the vertex).
2. Each Delaunay tetrahedron corresponds to one Voronoi vertex (the center of the tetrahedron is at the vertex).

I know each Delaunay face corresponds to one Voronoi edge, and I have the face vertices, but how do I get the Voronoi edge out of it?

Also, each Delaunay edge corresponds to one Voronoi face, but again - how do I find the face corresponding to the edge?

Answer 1

Let's consider an edge in the Delaunay triangulation. Assume for now it is not on the convex hull of the input points. Consider one tetrahedron incident to that edge. You get the first point of the dual face. Then choose one of the two triangles in the tetrahedron incident to the edge. Cross it and you'll be inside another tetrahedron which gives you the second point of the face. If you keep turning around the edge like this (in the same direction) you'll be back in the first tetrahedron and you'll get the description of the face. If the edge is on the convex hull, you'll need to add rays instead of segments during the description of the face.

Note that if you have more than 3 co-spherical points, some tetrahedra will correspond to the same dual Voronoi vertex.