Introduction to Computational Geometry

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


DateReading (O'Rourke)Notes
01/29/20Chapter 1Triangulation
02/05/20Chapter 2Polygon Partitioning
02/10/20Polygon Partitioning
02/12/20Chapter 3Convex Hulls (2D)
02/17/20Convex Hulls (2D)
02/19/20Polygon Partitioning (Implementation)
02/24/20Chapter 4Convex Hulls (3D)
02/26/20Convex Hulls (3D)
03/02/20Convex Hulls (3D)
03/04/20Chapter 5Voronoi Diagrams and Delaunay Triangulations
03/09/20Voronoi Diagrams and Delaunay Triangulations
03/11/20Class Cancelled
03/16/20Spring Break
03/23/20Chapter 5Fortune's Algorithm (Video)
03/25/20Chapter 6Arrangments (Video)
03/30/20Arrangements (Video)
04/01/20Chapter 7Search and Intersection (Video)
04/06/20Search and Intersection (Video)
04/08/20Class Cancelled: Passover
04/13/20Chapter 7Search and Intersection (Video)
04/15/20Class Cancelled: Passover
04/20/20Chapter 8Motion Planning (Video)
04/22/20Motion Planning (Video)
04/27/20Motion Planning (Video)
04/29/20Chapter 7Search and Intersection (Video)