From: mwilson@orl.mmc.com (Mark Wilson)
Subject: Delauney Triangulation Summary
Reply-To: mwilson@orl.mmc.com
Organization: Martin Marietta Orlando
Date: Fri, 31 Jul 1992 14:55:10 GMT

Some time back I asked for info on Delauney triangulation. A compiled list of 
responses follows:

From: Martin Ameskamp <ma@informatik.uni-kiel.dbp.de>
there are dozens of algorithms around for that kind of thing, loads of papers
too. But there is also a program called voronoi in /netlib on
research.att.com (192.20.225.2). That works just fine.

From: hughes@s1.msi.umn.edu (Matt Hughes)
There is stuff on netlib (voronoi algorithm) and some
people at NSCA wrote some stuff on some alpha algorithm
that is similiar.

From: uselton@nas.nasa.gov (Samuel P. Uselton)
I believe there is a Voronoi triangulation (the dual of the Delauney)
in netlib.  I'd have to dig through things to find the exact instructions,
but basically you can send a msg asking for the index, then anon ftp
things that look interesting.

From: kenb@amc.com (Ken Birdwell)
"Implementing Watson's Algorithm in three Dimensions".
David A. Field
ACM, 2nd Annual Sympos. on Computational Geometry, 1986, pg 246.

From: Sridhar Vajapeyam <kutty@bach.udel.edu>
Are you looking for the implementation in 2 or 3 dimensions? If it's
two dimensions, then it's available from netlib. If it's 3-D, then I have
something I wrote in FORTRAN, but it's not properly documented and very
messy. For the relevant theory, check "Computational Geometry" by Preparata
and Shamos.
The book is published by Springer-Verlag (1985). It is a fairly common book - 
any decent univ/research library will have it. From what you said, I doubt 
that just a Delaunay Triangulation is what yu are looking for - the Del. Tr.
will just give you a bunch of non-intersecting tetrahedra that fill the convex
hull of the set of points.
	You are probably trying to construct a surface through a set of points
in 3-D.  That is a much more difficult thing  - it's part of what I am working
on for my PhD.  I have to run now, but will be glad to give you some references
to papers and stuff if you told me a bit more about what you want. For example,
are you trying to find the smoothest surface, or the minimum area surface, etc.

From: CHELLA@evax11.eng.fsu.edu
	You can get the VORONOI programs from netlib. A good general 
technical reference is the book " Computational Geometry" by Preparata 
and Shamos. Also: Green and Sibson: Computing Dirichlet tessellations in 
the plane. The Computer Journal, 21(2):168-173, 1978.
	I am looking for a program to triangulate the interior of an 
arbitrary planar region. If you come across one, I would appreciate the 
information.

From: kenv%garcon@sun.com (Ken Vollmar)
A detailed survey paper with references to Delauney triangulation is
    "Voronoi Diagrams -- A Survey of a Fundamental Geometric Data Structure" 
    Franz Aurenhammer, ACM Computing Surveys, Vol.23, No.3, Sept.1991, 
    pp. 345-405.  
In particular, see the section beginning on p. 357. This doesn't directly
discuss any implementations.

An algorithm is described in 
    "Computing Dirichlet tesselations in the plane." P.J.Green and R. Sibson,
    Computer Journal.  Vol. 21, May 1978, p. 168-173.

Please post your results to news, especially implementations.

Per the above request, these are the compiled responses. Sorry this is slow
in posting. 

----------------------------------------------------------------------
Mark Wilson                              Martin Marietta E,I & M Group
mwilson@orl.mmc.com                      Mail Point 170
Phone: (407)356-6386                     P.O. Box 555837
Fax:   (407)436-5482                     Orlando, FL, 32855-5837
My opinions are my opinions, Martin Marietta can speak for itself.

Newsgroups: comp.graphics