15-853: Algorithms in the Real World (Guy Blelloch, Fall 99)

#

Topic 5: Triangulation

[ Topics |
Scribe Notes |
Readings |
Text Books |
Links ]

Triangulation 1 (draft) (Aaron Brown)
Triangulation 2 (Franklin Cho)
Triangulation 3 (draft) (Michael Downes)
O'Rourke.
Computational Geometry in C.
Cambridge University Press, 1994.
**Chapter 5** (Voronoi Diagrams)
Scot Drysdale, Voronoi Diagrams: Applications from Archaology to Zoology.
Review the applications described in Eppstein's
Delaunay,
and
Voronoi
Diagram pages.
**Primary**
M. de Berg, M. van Kreveld M. Overmars, and O. Schwarzkopf.
Computational Geometry, Algorithms and Applications.
Springer-Verlag, 1997.
**Others** (alphabetical order)
J. E. Goodman, and J. O'Rourke (Editors).
Handbook of Discrete and Computational Geometry
CRC Press, 1997.

A nice reference book.
K. Mulmuley.
Computational Geometry: An Introduction Through Randomized Algorithms.
Prentice Hall, 1994.
J. Nievergelt and K. Hinrichs.
Algorithms and data structures:
with applications to graphics and geometry.
Prentice Hall, 1993.
J. Pach and P.K. Agarwal.
Combinatorial Geometry.
John Wiley and Sons, 1995.
Preparata, Franco P.
Computational geometry: an introduction.
Springer-Verlag, 1988.
A. Okabe, B. Boots, and K. Sugihara.
Spatial Tessellations: Concepts and Applications of Voronoi Diagrams.
John Wiley, 1992.
O'Rourke.
Computational Geometry in C.
Cambridge University Press, 1994.
**General links**
David Eppstein's
Geometry in
Action page. An **excellent** page on applications of computational geometry
Jeff Erickson's Computational Geometry Pages
David Dobkin's SCG/WACG plenary talk Computational
Geometry: Where did it Come From, What Is It, What is it Good For?" (slides)
Yahoo's Geometry page.
An experimental comparison of various Delaunay algorithms.
Includes MPEG movies of the algorithms in action (if you dare wait for them to arrive from Germany).
Application Challenges to Computational Geometry.
The Computational Geometry (CG) impact task force report. Gives a nice
description of the state-of-the-art in computational geometry (as of 1996).
Strategic Directions in Computational Geometry Working Group Report
**Survey Articles**
F. Aurenhammer, Voronoi diagrams-- a survey of a fundamental
geometric data structure, ACM Computing Surveys, 1991, 345--405.
S. Fortune, Voronoi diagrams and Delaunay triangulations, in
"Computing in Euclidean Geometry", 2nd edition, World
Scientific, 1995.
**Mesh Generation.**
A list of overview papers on mesh generation (and triangulation).
The Finite element mesh generation page
The Meshing Research Corner (by Steve Owen)
Finite element mesh generation.
Paul Heckbert's Collection of Mesh Generation Links
**Surface Modeling, Reconstruction and Interpolation**
A page on Multiresolution Modeling. This is an application of surface modeling to graphics.
A Survey of
terrain visualization software. This is a list
of about 100 products on the market that do terrain visualization.
A large number of them use Delaunay triangulation as a substep.
This survey was done by the military.
Application of Delaunay triangulation to Interpolation.
G. Barequet and M. Sharir, Piecewise-linear interpolation
between polygonal slices, 10th ACM Symp. Computational Geometry,
1994.
**Companies that sell products that use Delaunay triangulation**
A long list of grid generators at Silicon Graphics.
ANSYS
SDRC
ICEM CFD
Fluent (Rampant)

Back to the Algorithms in the Real World home page.

Guy Blelloch,
guyb@cs.cmu.edu.