voronoi diagram on a sphere


does anyone out there happen to know how one would go by building a voronoi diagram on a sphere? The "sites" of the diagram are on the unit sphere. Some effort has been put into the problem, and I have actually three ideas on how to proceed :

1/ With Fortune's algorithm
I tried to transpose Fortune's line-sweep algorithm to the surface of a sphere, but I got stuck on a mathematical problem, some formula that is supposed to define the surface that separates space in two, all points of space closer to a given point on the sphere on one side, and all points closer to circle on the sphere (not a great circle, just any circle - an intersection between the sphere and a plane). It looks like this :
Ax + By + Cz + Dsqrt(1-y^2) = 0
To implement the algorithm, I need to determine an intersection between two such things and I really don't know how to manipulate them (the sqrt(1-y^2) term being the problem).

2/ Using a Delaunay triangulation instead
It seems that it would be easier to implement on a sphere since the math is more intuitive, at least in the incremental algorithms I've seen. But even though the algorithm would be of the same average complexity as Fortune's algorithm - O(n log(n)) - it seems it would be a lot slower given all the intersection tests required.

3/ Using Fortune's algorithm, but this time on a 2D stereographic projection of the sphere
I think the idea is cool but I need some proof that it would give the same output. The stereographic projection doesn't preserve distances which is kind of a central theme in Voronoi diagrams. On the other hand, I get the feeling that it should work on a Delauney triangulation, and if it works for one, it works for the other... I just lack the math "intuition" to prove one way or the other.

Well, I hope someone can help me out, and I hope this is posted in the right place.
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!