From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA26197; Wed, 16 Oct 2002 12:10:33 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA25551 for ; Wed, 16 Oct 2002 12:10:33 +0200 (MET DST) Received: from chimta03.algx.net (chimta03.algx.net [216.99.233.78]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g9GAAW523788 for ; Wed, 16 Oct 2002 12:10:32 +0200 (MET DST) Received: from d226.focal3.interaccess.com (d226.focal3.interaccess.com [207.208.138.226]) by chimmx03.algx.net (iPlanet Messaging Server 5.1 HotFix 1.4 (built Aug 5 2002)) with SMTP id <0H42005GTK4L92@chimmx03.algx.net> for caml-list@inria.fr; Wed, 16 Oct 2002 05:07:43 -0500 (CDT) Date: Wed, 16 Oct 2002 10:09:59 +0000 (GMT) From: olczyk@interaccess.com (Thaddeus L. Olczyk) Subject: [Caml-list] [OT] ICFP and Vornoi diagrams. To: caml-list@inria.fr Reply-to: olczyk@interaccess.com Message-id: <3daf3aeb.738441953@smtp.interaccess.com> Organization: stickit@nospammers.com MIME-version: 1.0 X-Mailer: Forte Agent 1.5/32.451 Content-type: text/plain; charset=us-ascii Content-transfer-encoding: 7BIT Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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