Algorithm to compute a Voronoi diagram on a sphere

Question

I'm looking for a simple (if exists) algorithm to find the Voronoi diagram for a set of points on the surface of a sphere. Source code would be great. I'm a Delphi man (yes, I know...), but I eat C-code too.

Answer 1

It's been a while since the question has been answered, but I've found two papers that implement Fortune's algorithm (efficiency O(N lg N), memory O(N)) over the surface of the sphere. Maybe a future viewer will find this information useful.

• "Sweeping the Sphere" by Dinis and Mamede, published in the 2010 International Symposium on Voronoi Diagrams in Science and Engineering. Can be purchased at http://dx.doi.org/10.1109/ISVD.2010.32
• "A Plane Sweep Algorithm for the Voronoi Tessellation of the Sphere" by Zheng et al. I'm not sure it was published because of the first one, but it is dated 13 December 2011. It is available for free at http://www.e-lc.org/tmp/Xiaoyu__Zheng_2011_12_05_14_35_11.pdf

I'm working through them myself at the moment, so I can't explain it well. The basic idea is that Fortune's algorithm works on the surface of the sphere so long as you calculate the points' bounding parabolas correctly. Because the surface of the sphere wraps, you can also use a circular list to contain the beach line and not worry about handling cells at the edge of rectangular space. With that, you can sweep from the north pole of the sphere to the south and back up again, skipping to sites that introduce new points to the beach line (adding a parabola to the beach line) or the introduction of cell vertices (removing a parabola from the beach line).

Both papers expect a high level of comfort with linear algebra to understand the concepts, and they both keep losing me at the point they start explaining the algorithm itself. Neither provide source code, unfortunately.

Answer 2

Quoting from this reference: http://www.qhull.org/html/qdelaun.htm

To compute the Delaunay triangulation of points on a sphere, compute their convex hull. If the sphere is the unit sphere at the origin, the facet normals are the Voronoi vertices of the input.

Answer 3

CGAL is working on the "spherical kernel" package, which would allow to compute exactly these kind of things. Unfortunately, is not released yet, but maybe it will be in their next release, since they already mentioned it in a google tech talk in march

Answer 4

Here's a paper on spherical Voronoi diagrams.

Or if you grok Fortran (bleah!) there's this site.

Answer 5

In short, try cssgrid from NCAR Graphics. I wrote a longer answer for a similar question at codereview.stackexchange.com.