Description
PyData London 2016
Spherical Voronoi diagrams partition the surface of a sphere into regions of closest distance to a set of generator points. As discussed by Tyler Reddy at PyData 2015, there was no ready-to-go implementation of this in Python. After a self-contained introduction, we will tell the story about how this talk led to an extension of scipy to handle this problem.
Imagine you are in London and want to travel somewhere within London. Your smartphone ran out of battery and you are not familiar with the area. So you just go the closest tube station. In this manner, you could get a map of London partitioned into regions of closest distance to the various tube stations. Mathematically, this is called a Voronoi diagram. It is defined by a finite set of points in the plane, which are called generators (the tube stations in this example), and consists of a finite number of polygons representing the regions of closest distance to the generators (see Wikipedia for pictures and more details). Calculating Voronoi diagrams in the plane is a well known problem in computational geometry and can be easily handled in Python using scipy.spatial.Voronoi.
Imagine you are in London and want to travel to some destination far away. Since you are close to an airport, you want to go by plane. In a similar fashion, the airports partition the surface of the Earth into regions of closest distance. Mathematically, this is called a spherical Voronoi diagram. Analogously, this is defined by a finite set of generator points on a sphere and consists of finitely many spherical polygons representing the regions of closest spherical distance to the generator points. (Play with this online sandbox if you like.)
At PyData London 2015, Tyler Reddy discussed the problem of calculating spherical Voronoi diagrams in Python in this talk. While the problem had been studied and solved conceptually by various computer scientists, there was no ready-to-go implementation available in Python. This initiated a collaboration, which ultimately led to the creation of scipy.spatial.SphericalVoronoi.
This talk will give a self-contained introduction to the topic of Voronoi diagrams and tell the story of the pull request mentioned above. We will also highlight some applications of spherical Voronoi diagrams in computational virology aimed at getting a better insight into the Dengue virus and Hepatitis C, which was Tylers original motivation to consider the problem.
Slides available here: http://www.nullteilerfrei.de/%7Eairwalker/pydata2016/spherical_voronoi.pdf
GitHub Repo: https://github.com/niknow/pydata-london-2016-voronoi