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

next up previous
Topic 5: Triangulation

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

Topic Outline

  • Introduction
  • Basic geometric operations (in-circle, line-side)
  • Convex Hulls in 2 and 3 dimensions
  • Definition and properties of Voronoi Diagrams and Delaunay Triangulation
  • Algorithms
  • Intersection of Halfplanes
  • Radial Sweep
  • Incremental construction
  • Divide-and-Conquer (work done on merging)
  • Divide-and-Conquer (work done on divide)
  • Plane Sweep
  • Applications
  • Finite element meshing
  • Statistical structure prediction of proteins
  • Surface reconstruction and Interpolation
  • 2-d geographic surface approximation
  • Interpolating sparse geoscientific datasets
  • Medical imaging

    • Scribe Notes

  • Triangulation 1 (draft) (Aaron Brown)
  • Triangulation 2 (Franklin Cho)
  • Triangulation 3 (draft) (Michael Downes)

    • Readings

  • 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.

    • Recommended Text Books

    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.

    • Further Readings and Links

  • 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.