Introduction to Computational Geometry (Com S 418/518)

This course is primarily based on Mark de Berg et al's popular text  Computational Geometry: Algorithms and Applications (3rd edition) on the subject.  My lecture notes are made available below in both PowerPoint and PDF formats in case you may find useful. 

  1. Basic algorithms 

  2. Geometric data structures and queries

  3. Overlay, polygon triangulation, and half-plane intersection

    • Overlay of two subdivisions (pptxpdf)

    • The Art Gallery problem (pptxpdf)

    • Polygon triangulation (pptxpdf)

    • Half-plane intersection (pptx​​​​​​​, pdf)

  4. Two-variable linear programming

  5. Voronoi diagrams and Delaunay triangulations

  6. Duality, line arrangements, convex hulls, and envelopes

  7. Path planning