GeomDir       Blue Ribbon Campaign

This is a small collection of computational geometry software, papers, and resources.
Official URL:
Provider: Ernst Mücke, <>.



Sources to the latest version of Detri. The code constructs the 3D Delaunay triangulation of a given point set using a variant of the randomized incremental-flip algorithm [J91,ES96,M93]. It achieves robustness by using the SoS symbolic perturbation method [EM90]. Valid input data consists of point sets in arbitrary position, given either in integer or fix-point coordinates. The distribution includes:

Download and uncompress Detri_2.6.a.tar.gz using 'gzip -d'; then type:
        tar xvfp Detri_2.6.a.tar
        cd Detri_2.6.a/detri/
        make detri_new [CC="gcc [-ansi]"]
        cd ../..
The ANSI C sources compile as they are on SGI, SUN, and NeXT workstations (use 'make detri_new CC=gcc' on SUNs); the executable will be in Detri_2.6.a/bin/. You can use the collection of data files below for test data.

There is some documentation in form of README files in each of the subdirectories.

Report any problemos to <>.

Fast Randomized Point Location in Delaunay Triangulations

Postscript version of our paper analysing the 3D "jump-and-walk" procedure for point location in Delaunay triangulations [MSZ96]. This procedure finds the query point simply by "walking through" the triangulation, after selecting a ``good starting point'' by random sampling. It is hard to imagine to anybody could come up with an algorithm that would be easier to implement; plus, the jump'n'walk scheme does not require any preprocessing nor any additional storage. Nevertheless, empirical results in both two and three dimensions show that this procedure is efficient in practice, and our theoretical results of an elaborate probabilistic analysis do not contradict this either.

Alpha Shapes: Definition and Software

HTML version of a summary paper which appeared in the Proceedings of the 1st International Computational Geometry Software Workshop at the Geometry Center, January 1995 [AE*95]. It is a brief introduction to Alpha shapes.

The 3D Alpha shape software is no longer kept in this directory. It can, however, be downloded from at NCSA.

If you have any questions, ask <> or <>.

Three-dimensional Alpha shapes

Postscript version of the ACM TOG paper on 3D Alpha Shapes [EM94]. Depending on disk space availability of the server, there might also be a file containing rather low quality B&W scans of the color plates of the journal version. If this file is not available, do not despair, downloading the Alpha shape software is a far better way to explore the world of Alpha shapes.

Simulation of Simplicity

Postscript version of the ACM TOG paper on the SoS symbolic perturbation technique to cope with degenerate cases in geometric algorithms [EM90].


A collection of sample data files for the Detri and unweighted Alpha shape code. Uncompress and un-tar the file to get a directory data/sample_data/ with data files.


Harald Rosenberger's Pascal (and partly C) sources implementing the Beneath-Beyond method for convex hulls in 3D and 4D, using an old version of SoS (this part of the code is written in C). Since Harald is no longer in the United States, this code is not supported at all. You are completely on your own! Take the file, uncompress and un-tar it; this will create the directories ch/, ch/ch3/, ch/ch4/, and ch/sos/, containing the sources. A good reference for the algorithm would be [E87]. File ch.sun.tar.gz contains the SUN Sparc binaries of ch3 and ch4.


[AE*95] Nataraj Akkiraju, Herbert Edelsbrunner, Mike Facello,
        Ping Fu, Ernst Mücke and Carlos Varela. Alpha Shapes:
        Definition and Software. Extended abstract in Proceedings
        of the 1st International Computational Geometry Software
        Workshop, pages 63-66, 1995.

[E87]   Herbert Edelsbrunner.  Algorithms in Combinatorial Geometry.
        Springer Verlag, Heidelberg, 1987.

[EM94]  Herbert Edelsbrunner and Ernst Mücke. Three-dimensional alpha
        shapes. ACM Transaction on Graphics, 13(1):43-72, 1994.

[EM90]  Herbert Edelsbrunner and Ernst Mücke. Simulation of Simplicity:
        A technique to cope with degenerate cases in geometric algorithms.
        ACM Transactions on Graphics, 9(1):66-104, 1990.

[ES96]  Herbert Edelsbrunner and Nimish Shah.  Incremental topological
        flipping works for regular triangulations. Algorithmica,
	15:223-241, 1996.

[J91]   Barry Joe. Construction of three-dimensional Delaunay triangulations
        using local transformations.  Computer Aided Geometric Design,
        8(2):123-142, 1991.

[MSZ96] Ernst Mücke, Isaac Saias and Binahi Zhu.  Fast Randomized
        Point Location Without Preprocessing in Two- and Three-dimensional
        Delaunay Triangulations.  Proceedings of the 12th Annual Symposium
        on Computational Geometry, pages ??-??, 1996.

[M93]   Ernst Mücke.  Shapes and Implementations in Three-Dimensional
        Geometry.  PhD Thesis.  Department of Computer Science,
        University of Illinois at Urbana-Champaign, 1993. 
        Also: Technical Report UIUCDCS-R-93-1836