Introduction to Computational Geometry

Instructor: Don Sheehy
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

  1. What is Computational Geometry
  2. Linear Predicates
  3. More on Determinants and Linear Predicates
  4. Convex Hulls in the Plane
  5. Simple Polygons and the Jordan Curve Theorem
  6. Planar Straight-Line Graphs
  7. Data Structures for Planar Straight-Line Graphs
  8. Posets, Duality, and Barycentric Coordinates
  9. Polyhedral Complexes and Triangulations of Point Sets
  10. Delaunay Triangulations of Point Sets
  11. Incremental Delaunay Triangulation
  12. Randomized Incremental Delaunay Triangulation
  13. Voronoi Diagrams
  14. Introduction to Projective Duality
  15. Exercises in Projective Duality
  16. Halfspace Range Counting
  17. Point Location in a Planar Subdivision
  18. Tutte's Algorithm I
  19. Tutte's Algorithm II
  20. The Maxwell-Ceremona Correspondence
  21. Steinitz's Theorem
  22. Weighted Delaunay Triangulations
  23. Koebe Embeddings
  24. From Low Dimensions to High Dimensions