Voronoi diagram using custom (large circle) distance

Question

I want to create a Voronoi diagram for several pairs of latitude / longitude, but want to use the large circle distance between them, and not the (inaccurate) Pythagorean distance.

Is it possible to make qhull / qvoronoi or some other Linux program?

I examined the display of points in 3D, having qvoronoi, creating 3D Voronoi Diagrams [1] and intersecting the result with a unit sphere, but I'm not sure if this is easy.

[1] I understand the three-dimensional distance between two latitudes / longitudes ("on the ground") does not coincide with the distance of a large circle, but it is easy to prove that this transformation preserves the relative distances, which is all that matters for the Voronoi diagram.

Answer 1

I assume you found this article . From this, it seems you have the right idea using 3D embedding. Your question is how to cross the result using a sphere.

First of all, you need to think about how you are 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 it might be best to just use a 3D view.

If you use a program like qvoronoi, theoretically you only need inifinite hyperphilic data (generated by Fo ). This gives you the equation of the plane and the two points that it corresponds to. Usually you need to use the voronoi diagram to check for inclusion in the regions, and hyperplanes are enough for this.

Answer 2

See also this question: Algorithm for calculating the Voronoi diagram on a sphere?