Introduction to Computational Geometry
(600.459)

• Meeting Time: Monday and Wedensday 1:30-2:45
• Meeting Place: Maryland 214
• TA: Fabian Prada
• Textbook (required): Computational Geometry in C, O'Rourke.
• Textbook (optional): Computational Geometry, de Berg et al.

Assignments

• Polygon Triangulation: 02/21/16
• Convex Hull (2D) Calculation: 03/13/16
• Convex Hull (3D) and Delaunay Triangulation (2D) Calculation: 05/05/16

• QHull
• ANN: A Library for Approximate Nearest Neighbor Searching
• Triangle
• TetGen
• Computational Geometry Algorithms Library

• Convex Hulls of Finite Points in Two and Three Dimensions, Preparata and Hong (1977)
• Medial Axis Transformation of a Planar Shape, Lee (1982)
• A New Linear Algorithm for Intersecting Convex Polygons, O'Rourke, Chien, Olson, and Naddor (1982)
• Fast Detection of Polyhedral Intersection, Dobkin and Kirpkpatrick (1983)
• Intersection of Convex Objects in Two and Three Dimensions, Chazelle (1987)
• Constrained Delaunay Triangulations, Chew (1987)
• Power Diagrams: Properties, Algorithms and Applications
• Art Gallery Theorems and Algorithms, O'Rourke (1987)
• Provably Good Mesh Generation, Bern et al. (1990)
• Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure, Aurenhammer (1991)
• Triangulating a Nonconvex Polytope, Chazelle et al. (1992)
• Quality Mesh Generation in Three Dimensions, Mitchell et al. (1992)
• Three-Dimensional Alpha Shapes, Edelsbrunner et al. (1994)
• Algorithms for Ham-Sandwich Cuts, Lo et al. (1994)
• Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions, Chan (1996)
• Delaunay Refinement Mesh Generation, Shewchuk (1997)
• Tetrahedral Mesh Generation by Delaunay Refinement, Shewchuk (1998)
• A Minimalist's Implementation of the 3-d Divide-and-Conquer Convex Hull Algorithm, Chan (2003)