generating Voronoi polygons

[Seth Teller]

In article <9101190311.AA08355 at nazgul.physics.mcgill.ca> loki at NAZGUL.PHYSICS.MCGILL.CA (Loki Jorgenson Rm421) writes:
>> looking for software to generate Voronoi polygons (also known as
>> Dirichlet tesselations) from a set of generating points in two dimensions.
>> any portion of the required algorithms would be appreciated.

an interactive voronoi program for sgi boxes is available through
anonymous ftp from the new ftp.brl.mil (internet 128.63.16.158) 
in pub/voronoi.tar.Z.

the program is about 10K lines of c code, fully interactive,
etc. it's based on steve fortune's sweepline algorithm and
non-interactive implementation.  the interactive version
displays voronoi diagrams, delaunay triangulations, convex
hulls, and the connection between d-dimensional voronoi
diagrams and (d+1)-dimensional convex hulls of co-spherical 
points (where d=2). some references:

        s.j. fortune, "a sweepline algorithm for voronoi diagrams,"
algorithmica 2 (1987), 153-174.

	f.p. preparata & m.i. shamos, _computational geometry: an
introduction_, springer-verlag, 1985, pp. 246-248.

for those who don't want thousands of pounds of gl and ui code,
there's a c library version in vregion.tar.Z that supports queries
for voronoi regions and delaunay triangles.

seth