(600.459/659)

This course will provide an introduction to computational geometry. It will cover a number of topics in two- and three-dimensions, including polygon triangulations and partitions, convex hulls, Delaunay and Voronoi diagrams, arrangements, and spatial querries. Students are encouraged to complete the assigned reading before class, and will be required to implement a number of the discussed techniques. (Audits will not be allowed.)

- Meeting Time: Monday and Wedensday 1:30-2:45
- Meeting Place: Zoom
- TA: Tommy Mitchel
- Textbook (optional): Computational Geometry in C,
*O'Rourke*. - Textbook (optional): Computational Geometry,
*de Berg et al.*

- Polygon Triangulation:
**(02/27/20)** - Convex Hull (2D) Calculation:
**(03/25/20)** - Convex Hull (3D) and Delaunay Triangulation (2D) Calculation:
**(05/04/20)**

- 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)
- Exact and Efficient Construction of Planar Minkowski Sums Using the Convolution Method, Wein (2006)