From: Jeff Erickson Newsgroups: comp.graphics.algorithms,sci.math.num-analysis Subject: Re: Voronoi diagrams of convex sites Date: Thu, 17 Dec 1998 11:46:06 -0600 ACARY wrote: > I'm searching for algorithms which compute Voroinoi diagrams for a set > of line segments and convex polygons. > Where Can I find informations about such algorithm ( Stability, > robustness, implementation ). Probably the most robust and stable implementation in existence is by Martin Held, described in his paper ``Voronoi Diagrams and Offset Curves of Curvilinear Polygons'', Comput. Aided Design 30(4):287-300, 1998. Once nice feature of this algorithm is that it also handles polygons with circular-arc edges almost for free. You can see some examples of his algorithm's output at http://www.cosy.sbg.ac.at/~held/projects/voronoi_2d/voronoi.html You can't download his Voronoi diagram code off the web, but you can get it by sending him email. -- Jeff Erickson jeffe@cs.uiuc.edu Computer Science Department http://www.uiuc.edu/ph/www/jeffe University of Illinois, Urbana-Champaign