Howdy, Stranger!

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

Categories

voronoi diagram on a sphere

schmiley397schmiley397 Member Posts: 3
hi,

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.
cheers
Sign In or Register to comment.