**Up:** *Directory of Computational Geometry Software*

## Low dimensional convex hull, Voronoi diagram and Delaunay triangulation

There are other excellent
Delaunay triangulation programs on the
triangulation page.
In three or higher dimensions, you should
consider the
arbitrary dimensional programs, some of which are very good.
Finally, you might be interested in
constrained Delaunay triangulation,
trapezoidation or some other operation on
polygons.

### Detri

Robust Delaunay tetrahedralization of 3-D point sets.
Randomized incremental flipping algorithm.
Achieves robustness using symbolic perturbation
(so good on degenerate input).
Executables for SGI and Sun, and C sources available.
There's a short
paper about this program.

You can download *Detri*
from Ernst's
GeomDir
directory. It also contains papers about *Simulation
of Simplicity* (the symbolic perturbation method employed) and
3D alpha shapes.
By Ernst Mücke, then at the University of Illinois at
Urbana-Champaign.

### DeWall, InCode

Two three-dimensional Delauney triangulation algorithms,
one divide and conquer, the other incremental.
Uses a uniform grid to speed up the decomposition and insertion,
respectively, so should be good on well-distributed points.
Can not handle degenerate data.
In ANSI C.
For pointers to the code, see the
Web page.
By P. Cignoni, C. Montani and R. Scopigno, of the CNR, Pisa, Italy.

### tess

Delaunay tetrahedralization of 3-D point set using a
gift-wrapping algorithm. In C. Floating point with
careful attention to numerical stability, but not guaranteed
to handle degenerate input.
There's more information in the
README file.

Get *tess* from our ftp directory.
By Carol Hazelwood, Southwest Texas State University.

### Delaunay tree

Computes a randomized dynamic data structure for Delaunay triangulations
in either two or three dimensions. Randomized dynamic in this case means
that you can insert a new point in expected *O(lg n)* time and delete
a random point in expected *O(lg n lg lg n)* time.
In C++ using LEDA.
Some documentation (French and English) in the tar files, which you
can download from
INRIA.

By
Olivier Devillers, INRIA.

### 2D Delaunay triangulation and Voronoi diagram and 3D convex hull

The classic here is Steve Fortune's
voronoi program.
Implements Fortune's planesweep algorithm.
in C using floating-point arithmetic.
There is more information on the
manpage .

Steve Fortune is at Bell Labs.

You can get the source code by mailing *
send sweep2 from voronoi* to the address * netlib@research.att.com*.

See Graphics Gems IV for
an incremental 2D Delaunay triangulation program
by Dani Lischinski,
at the University of Washington.

Computational Geometry in C has a
a very simple $O(n^3)$ two dimensional Delaunay triangulation program
by Joe O'Rourke
at Smith College.

David Watson
lets you download his small C program for two and three dimensional
Voronoi diagram and Delaunay triangulation from his homepage, which
also has some interesting information about applications in
geology.

At the bottom of
this page, there is a pointer to another short floating-point
implemenation of the Guibas-Stolfi Delaunay triangulation algorithm.
By Geoff Leach, at RMIT, Australia.

### 3d convex hull

A nice incremental three-dimensional convex hull program,
from Computational Geometry in C,
by Joe O'Rourke.

### 2D convex hulls

Here is a short, robust O(n lg n) two-dimensional
convex hull program, in C. You could print it on the
back of a business card.
By Ken Clarkson, at Bell Labs.

There is a two-dimensional convex hull program
in Computational Geometry in C,
by Joe O'Rourke. Uses Graham's scan algorithm, also $O(n lg n)$.

**Up:** *Directory of Computational Geometry Software*

*The Geometry Center Home Page*
Comments to: nina@geom.umn.edu