Voronoi Diagrams

Euclidean Voronoi Diagram for Circles in 2D

In 2001, we have published a pair of papers in Computer Aided Geometric Design journal, discussing an algorithm to compute Euclidean Voronoi diagram for circles. Shown in the following figure are examples computed from our algorithm. The algorithm is based on an exact computation paradigm and takes advantage of edge-flipping based on the solution of Apollonius 10th problem. We have shown that the algorithm can compute the desired Voronoi diagram in O(N²) without failure. In the middle of the development, the famous Apollonius 10th Problem (a problem to compute circles tangent to three circles) was also solved via Mobius mapping between complex planes.

Figure 1: Circle set Voronoi diagram

The Voronoi diagram for circles can be applied to various geometric problems such as cable packing problem, shortest path problem, and widest channel problem.

Figure 2: Cable packing problem

Figure 3: Shortest path problem

Figure 4: Largest channel problem

Euclidean Voronoi Diagram for Spheres in 3D

We have developed and implemented an algorithm which constructs Euclidean Voronoi diagram for spheres in 3-dimensional space by tracing Voronoi edges. Once such a Voronoi diagram is constructed, various spatial queries can be answered most efficiently and exactly. Shown in the following figure is a snapshot of such Voronoi diagram in our software developed.

Figure 5: Voronoi faces for sphere set

Figure 6: Sphere set Voronoi Diagram

This Voronoi diagram can be a useful tool to analyze the structural properties of proteins, and therefore we have developed and included various algorithms using the Voronoi diagram in our software for the purpose of analyzing protein structure such as defining protein-protein interface, finding largest empty space, constructing molecular surface, etc.

Figure 7: Seperating faces of atoms into two different groups

Figure 8: Internal voids

Figure 9: Molecular surface