Delaunay Triangulation
The Delaunay triangulation of a point set is a collection of edges
satisfying an "empty circle" property: for each edge we can find
a circle containing the edge's endpoints but not containing any other points.
These diagrams their and their duals (Voronoi
diagrams and medial axes)) have
been reinvented, given different names, generalized, studied, and
applied many times over in many different fields. The Delaunay triangulation is also closely related by the so-called "lifting transformation" to
convex hulls in one higher dimension.
Many common methods for
function interpolation and
mesh generation
are based in some way on Delaunay triangulations, but there are
also many other ways in which this structure has been applied.
-
Applications of 3d Delaunay triangulation algorithms in geoscientific modeling, R. Lattuada and J. Raper.
Uses 3d DT for shape reconstruction of 3d geographic objects such as aquifers, ocean currents, and weather fronts.
- Convex hull,
Voronoi diagram, and Delaunay triangulation software
from
Nina Amenta's CG software directory.
- Delaunay interpolation.
Various people discuss the pros and cons of using Delaunay triangulation
for data interpolatation.
- A Delaunay refinement algorithm for quality
2-dimensional mesh generation, Jim Ruppert, NASA.
- Delaunay triangulations in two and three dimensions.
Master thesis by Jörg Krämer
lists applications including crystal growth, metallurgy, cartography,
mesh generation, stereolithography, and visualization.
- Dynamic Weighted
Delaunay Triangulations for Efficient Collision
Detection in Distinct Element Modeling and
Simulation of Granular Media,
Jean-Albert Ferrez, EPFL.
- Geometric morphology of granular materials.
B. R. Schlei, L. Prasad, and A. N. Skourikhine
use constrained Delaunay meshing and chordal axis transforms
to identify grains and determine statistical features
in micrographs of porous media in order to obtain input for
hydrodynamic calculations.
For more information,
see Schlei's web site,
and their additional papers
"A
geometric transform for shape feature extraction" and
"Feature-based syntactic and metric shape recognition".
- The Gnu Triangulated Surface library. Providing robust primitives for mesh representation, constructive solid geometry operations, and Delaunay triangulation.
- Delaunay-based methods in mesh generation, from Steve Owen's
Meshing
Research Corner.
- Qhull software for
convex hulls, Delaunay triangulations, Voronoi diagrams, and halfspace
intersection about a point.
- SimplicialVIEW, a package for robust stability
analysis, uses Delaunay triangulations as part of an iterative
refinement sheme to approximate the crossover of a robust control problem.
- Skeleton and
boundary extraction. Glynn Robinson of Yale overlays the Delaunay
triangulation and Voronoi diagram of points sampled from a surface
(the boundary between different features in a medical image) and
somehow extracts from them subsets representing the surface itself and
its medial axis.
- Spatial
modelling by Delaunay networks. Terje Midtbø explains applications
of Voronoi diagrams to "subjects such as determination of areas covered
by a mobile telephone transmitter, determination of high-water marks in
rivers, determination of noise zones along roads, drawing voltage maps,
and other, more conventional cartographic tasks."
- Statistical
Geometry of Protein Structure. I. Vaisman performs statistical analysis
on Delaunay triangulations of protein atoms to find preferred clusters
of amino acids.
- Topological
Disorder and Conductance Fluctuations in Thin Films. K. Abkemeier
and D. Grier use Delaunay triangulations of randomly perturbed lattice points
to form resistor networks that model the electrical behavior of
amorphous and polycrystalline silicon.
- Triangle,
an incremental Delaunay-based 2d mesh generator
by Jonathan Shewchuk of CMU,
part of the
CMU Archimedes project for unstructured finite element computation.
- Visualizing 3D spatial patterns of archaeological assemblages.
Diego Jiminez and Dave Chapman use beta-skeletons and other Delaunay-like proximity graphs
to find potential semantic connections between Mexican artifacts.
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
