Official URL: http://www.geom.umn.edu/locate/cglist/GeomDir

Provider: Ernst Mücke, <epm@ansys.com>.

- Source code
- Robust 3D Delaunay triangulations (ANSI C)
- A Sample of 3D Data Sets (Point Coordinates)
- Convex Hulls in 3&4D (Pascal)

- Papers

Detri_2.6.a.tar.gz

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:

- the Basic C Library: the author's very own collection of macros and utility functions which helped him to keep his sanity even though programming in C,
- the Lia Package: a pretty fast long-integer package, doing
`+`,`-`, and`*`only, provided the maximum size of any long-integer number, occuring during the upcoming computation, is known in advance, and - the SoS Library: an implementation of a set of relevant SoS primitves.

tar xvfp Detri_2.6.a.tar cd Detri_2.6.a/detri/ make detri_new [CC="gcc [-ansi]"] cd ../..

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

Report any problemos to <epm@ansys.com>.

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 ftp://ftp.ncsa.uiuc.edu/Visualization/Alpha-shape/ at NCSA.

If you have any questions, ask <epm@ansys.com> or <alpha@ncsa.uiuc.edu>.

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]`.

data_1.1.tar.gz

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.

ch.src.tar.gz

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. URL: http://www.geom.umn.edu/~mucke/GeomDir/shapes95def/ [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. URL: http://www.geom.umn.edu/~mucke/GeomDir/shapes94.ps.gz [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. URL: http://www.geom.umn.edu/~mucke/GeomDir/sos90.ps.gz [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. URL: http://www.geom.umn.edu/~mucke/GeomDir/ptloc96.ps.gz [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 URL: ftp://cs.uiuc.edu/pub/TechReports/UIUCDCS-R-93-1836.ps.Z