[SciPy-Dev] Proposal: Spherical Voronoi Diagrams

[Tyler Reddy]

*Basic idea*: Implement spherical Voronoi diagram code in scipy.spatial,
which is where current computational geometry algorithms reside, including
Voronoi, ConvexHull, and Delaunay. Spherical Voronoi diagrams are extremely
useful for parsing spherical objects in biology (i.e., viruses), planetary
physics, search and rescue, airspace territory assignment, network
coverage, etc. The current planar Voronoi diagram code is not capable of
handling this.

*The current state of the code*: With plenty of helpful feedback after my
talk at PyData London 2015 presenting some of the challenges (
https://www.slideshare.net/slideshow/embed_code/key/1bKCEyHa789nBe), I've
been able to refine the code (
https://github.com/tylerjereddy/py_sphere_Voronoi). The algorithm and usage
examples are presented in the documentation (
http://py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html).
Empirical testing indicates that the algorithm exhibits quadratic time
complexity, while the best theoretical results in the literature are
loglinear. For several computational geometry calculations it is relatively
common to use a lower-performing algorithm if it is easier to implement.

The minimum number of input points (generators) tolerated is 4 and maximum
on a modern laptop is ~ 70,000 with 16 GB of physical memory. There are
probably a lot of opportunities to improve the code. I have some plots of
the current performance profiles, if needed. In many cases, the
reconstitution of spherical surface area achieved by summing the spherical
polygon (Voronoi region) surface areas is > 99 %. Nearly-degenerate Voronoi
regions (with vertices almost on top of each other) could perhaps be
handled more gracefully--they currently return areas of approximately 0.
The integrity of the code is currently maintained by a number of unit
tests.

*Question*: Is this perhaps of interest for integration into scipy? I
suspect the standards are pretty high to get the pull request for a whole
new functionality into the package, so I thought it best to inquire this
way first before the potentially substantial time investment of converting
the code to scipy standards from my current in-house layout. I know there
are guidelines I can follow for the pull request as well, but if there are
any basic suggestions from glancing at the current state of the code that
might be helpful as well.


Thanks,

Tyler
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20150802/3e5ffc0f/attachment.html>