Path: utzoo!attcan!uunet!lll-winken!ames!amelia!prandtl.nas.nasa.gov!kerlick
From: kerlick@prandtl.nas.nasa.gov (G David Kerlick)
Newsgroups: comp.graphics
Subject: Re: 2D-triangulation
Message-ID: <1404@amelia.nas.nasa.gov>
Date: 26 Jan 89 22:28:24 GMT
References: <11@opmvax.kpo.fi>
Sender: news@amelia.nas.nasa.gov
Reply-To: kerlick@prandtl.nas.nasa.gov (G David Kerlick)
Organization: NASA Ames Research Center
Lines: 46

Newsgroups: comp.graphics
Subject: Re: 2D-triangulation
Summary: 
Expires: 
SReferences: <11@opmvax.kpo.fi>
Sender: 
Reply-To: kerlick@prandtl.nas.nasa.gov (G David Kerlick)
Followup-To: 
Distribution: 
Organization: NASA Ames Research Center
Keywords: 

In article <11@opmvax.kpo.fi> hnevanlinna@opmvax.kpo.fi writes:
.Someone asked a few days ago for 3D-triangulation.
.I would be more than happy for an efficient algorithm for
.2D-triangulation.

What you are looking for is a Delaunay Triangulation
(with boundary it is called a Dirichlet Tesselation,
and its dual is a Voronoi Tesselation).

There is a method due to D.F. Watson which is of order 
O(N**(1 + 2/d)) where N is the number of points  and d 
is the spatial dimension.
There is a faster O(NlogN) algorithm of Guibas and
Stolfi which is, however, conceptually more complicated
and only works in the plane (d=2).

The subject of triangulations and data structures for them
is reviewed in:

Leila De Floriani

"Surface representations based on triangular grids"
The Visual Computer (1987) No.3 pp 27-50.
(published by Springer-Verlag)
which also has an extensive bibliography.


By the way, if anybody has working, public-domain
code for these, I'd like to see it as well!

The opinions expressed by NASA or the U.S. Government
are not necessarily those of the Author.

David Kerlick _ (415)-694-4779 _ kerlick@prandtl.nas.nasa.gov