Re: Triangulation Algo

From: Gill Barequet (barequet@cs.Technion.AC.IL)
Date: Sat Feb 27 1999 - 23:36:12 EET

On Sat, 27 Feb 1999 20:26:02 A.D.Bhatt wrote:

> A lot has been said about STL format. Can any one suggest some source for
> getting
> Solid or surface triangulation algorithms.

The amount of literature is extreme. A good survey is
   M. Bern and D. Eppstein,
   Mesh generation and optimal triangulation,
   in: Computing in Euclidean Geometry (F.K. Hwang and D.-Z. Du, eds.),
   World Scientific, 1992.

On Sat, 27 Feb 1999 10:58:21 -0500 aaroflex <> wrote:

> Triangulation or or more accurately called tessellation mathimatical
> representation was first set forth in 1937 by a Russian named Dulaney.

I am not aware to a Russian mathematician named Dulaney, and I apologize
for that in advance.
But I am aware of a famous French mathematician named Delaunay (1816-1872),
and indeed there is a Delaunay triangulation (or tessellation) of a set
of points in the plane.
This is the same as Dirichlet (1805-1859) tesselation.
This construction was rediscovered again and again in many fields. Most
notable is the Voronoi diagram (Voronoi, Russian, 1868-1908) which is
the dual construction of the Delaunay triangulation.
Triangulation was thus very popular already in the 19th century.

> During the 40s and 50s considerable thought was put to this subject, and
> several books were published, but the wave has passed.

I do not agree with the last statement. For example, the question whether
a simple planar polygon can be triangulated in linear time was settled
only in 1990. (The answer is yes.) The status of the minimum-weight
triangulation problem is still unknown. (It is not known whether it is
an NP problem or not.) Finally, mesh generation is an active field with
many annual conferences, mailing list, etc.


Gill Barequet, Ph.D. Phone: +972-4-829-3219
Faculty of Computer Science Fax: +972-4-822-1128
The Technion---IIT E-mail:
Haifa 32000 WWW:
                                "Life is NP-Hard." (-)

For more information about the rp-ml, see

This archive was generated by hypermail 2.1.2 : Tue Jun 05 2001 - 22:51:05 EEST