Finding polyhedron faces from edges

Question

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P).

A Voronoi diagram is a kind of tesselation that divided the medium into polygons in 2D and polyhedrons in 3D. I have Delaunay triangulation of a three-dimensional space. For the transition from Delaunay to Voronoi, firstly center of circumsphere of Delaunay tetrahedron is found (vertice) then edges linked to this center are determined. Founded edges are formed polyhedron faces.

I want to know: is there an algorithm that finds polyhedron faces from edges?

I will appreciate any comments that give me a little help and forgive me for writing shortcomings.

Answer 1

The Delaunay tetrahedralization and Voronoi diagrams are duals of each other with the following associations.

Delaunay	Voronoi
Tetrahedron	Vertex
Triangular Face	Edge
Edge	Polygonal Face
Vertex	Polyhedral Call

You can build the Voronoi objects in this table incrementally, to to bottom.

Voronoi Vertices

As you mention in the question, the Voronoi vertices are circumcenters of tetrahedron in the Delaunay tetrahedralization. Important in this step is to remember which Voronoi vertex is associated with which Delaunay tetrahedron (which we will use in the next step).

Voronoi Edges

Each Voronoi edge is associated with the face of in the Delaunay tetrahedralization. Specifically, each face in the Delaunay tetrahedralization belongs to two tetrahedra. The edge in the Voronoi diagram is connects the two Voronoi vertices associated with those tetrahedra. Again, remember the association between the new Voronoi edges and the Delaunay face.

Voronoi Faces

Each Voronoi face is associated with an edge in the Delaunay tetrahedralization. For an edge in the Delaunay tetrahedralization, we can look at the collection of Delaunay faces connected to the edge. These can be ordered, making a fan around the edge. Each Delaunay face is associated with a Voronoi edge. Using the same ordering, these Voronoi edges define the boundary of the associated Voronoi face.

This configuration is shown below. There is a Delaunay edge (red) between two Delaunay vertices (blue). The Delaunay faces connected to the edge are shown in transparent gray. Also displayed are the corresponding Voronoi face (green) and its edges (orange).

Voronoi Cells

Each Delaunay vertex is connected to a list of Delaunay edges. Each edge is associated with a Voronoi face. The collection of these associated Voronoi faces bound the Voronoi cell which is the dual of the Delaunay vertex.