Voronoi diagram using custom (great circle) distance

Question

I want to create a Voronoi diagram on several pairs of latitudes/longitudes, but want to use the great circle distance between them, not the (inaccurate) Pythagorean distance.

Can I make qhull/qvoronoi or some other Linux program do this?

I considered mapping the points to 3D, having qvoronoi create a 3D Voronoi diagram[1], and intersecting the result with the unit sphere, but I'm not sure that's easy.

[1] I realize the 3D distance between two latitudes/longitudes (the "through the Earth" path) isn't the same as the great circle distance, but it's easy to prove that this transformation preserves relative distances, which is all that matters for a Voronoi diagram.

Answer 1

I assume you've found this article. From that, it seems like you have the right idea by using a 3D embedding. Your question is then how to intersect the result with the sphere.

First of all you need to consider how you're going to represent the voronoi diagram. If you want to work in lat/long coordinates in a 2D plane, then your voronoi diagram will contain curved edges, so maybe it is best to just use a 3D representation.

If you use a program like qvoronoi, you should in theory only need the inifinite hyperplane data (generated by Fo). This gives you the equation of the plane and the two points it corresponds to. Usually you only need to use the voronoi diagram to test for inclusion within regions, and the hyperplanes should be enough for that.

Answer 2

See also this question: http://stackoverflow.com/questions/545870/algorithm-to-compute-a-voronoi-diagram-on-a-sphere