[Caml-list] [OT] ICFP and Vornoi diagrams.

[olczyk@interaccess.com (Thaddeus L. Olczyk)]

Sorry to post something off tipic but since mention of Delauny
triangulations and ICFP appeared here, I thought I would ask
a question that is bothering me.

( I also have no idea where else to ask. )

One of the web sites describes part of their algorithm as:
given a set of packages, we calculate the Vornoi diagram
of their destinations. Now we can find the Vornoi diagram
with a simple algorithm. Iterate over the points. At each 
iteration, for each calculate the region that is distance one 
greater than the previous calculation. When the calculated areas
touch that is a boudary. 

But this involves "painting" every reachable square.
So it is very expensive. On top of it, you have to examine all
posible permuations of packages. So the cost rises steeply.

So it would make sense to use an algorithm to calculate the
Vornoi diagram ( for example, examining the critical points
of the beach line ).But such algorithms only work on "empty" 
plains ie they assume that the line between two points is the 
distance. So it would seen not to be applicable.

 So how can we calculate the Vornoi diagram efrficiently.


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners