Introduction to Computational Geometry
Instructor: Don SheehyEmail: donald@engr.uconn.edu
Class Meets: MW 3-4:15 in Koons Hall 201 (map)
Office Hours: W 4:15-5:00
Office: ITEB 361
See the Course Policies.
The material covered this semester will differ some from the similar course last fall, but there will be some overlap.
Here are some links to the course website from previous years:
Computational Geometry - Fall 2013
Computational Geometry - Fall 2014
Lecture Notes
- What is Computational Geometry
- Linear Predicates
- More on Determinants and Linear Predicates
- Convex Hulls in the Plane
- Simple Polygons and the Jordan Curve Theorem
- Planar Straight-Line Graphs
- Data Structures for Planar Straight-Line Graphs
- Posets, Duality, and Barycentric Coordinates
- Polyhedral Complexes and Triangulations of Point Sets
- Delaunay Triangulations of Point Sets
- Incremental Delaunay Triangulation
- Randomized Incremental Delaunay Triangulation
- Voronoi Diagrams
- Introduction to Projective Duality
- Exercises in Projective Duality
- Halfspace Range Counting
- Point Location in a Planar Subdivision
- Tutte's Algorithm I
- Tutte's Algorithm II
- The Maxwell-Ceremona Correspondence
- Steinitz's Theorem
- Weighted Delaunay Triangulations
- Koebe Embeddings
- From Low Dimensions to High Dimensions