Veni, Vidi, Voronoi: attacking viruses using spherical Voronoi diagrams in Python

Tyler Reddy

Audience level:


Roughly spherical objects are abundant and affect human lives every day--whether dealing with the surface of the earth or microscopic viruses that cause severe illness in humans. Using spherical Voronoi diagrams, for which algorithms have only recently been proposed, we can gain insight into these objects. I will discuss an open source Python implementation and remaining challenges.


I've produced an open source Python implementation of the Voronoi diagram on the surface of a sphere. The ( "repository") and ( "documentation") are both available online. The code is capable of producing spherical Voronoi diagrams for a wide range of input test cases as verified by the unit tests, and further exposes the individual surface areas and coordinates of each Voronoi cell on the surface.

There are still some challenges to overcome, for which computational geometry and engineering expertise would be most welcome. For example, although the % surface area reconstitution when summing up the areas of the Voronoi cells is generally > 95 % of the theoretical surface area of the sphere, there are occasional (albeit rare) cases where a vertex is excluded from a Voronoi cell, leaving 'blank' spaces in the diagrams. There is also a general susceptibility to numerical / floating point instability in some of the calculations, presumably due to the substantial number of trigonometric operations. Again, input from experienced engineers and mathematicians would be most helpful in improving this open source effort.