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 

   • Geometric basics (pptx, pdf)

   • Convex hulls in 2D (pptx, pdf)

   • Line segment intersection (pptx, pdf)

2. Geometric data structures and queries

   • Doubly-connected edge list (pptx, pdf)

   • Kd-trees (pptx, pdf)

   • Range trees (pptx, pdf)

   • Point location (pptx, pdf)

   • Trapezoidal maps (pptx, pdf)

   • Interval trees (pptx, pdf)

   • Priority search trees (pptx, pdf)

   • Segment trees (pptx, pdf)

   • Quadtrees (pptx, pdf)

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

   • Overlay of two subdivisions (pptx, pdf)

   • The Art Gallery problem (pptx, pdf)

   • Polygon triangulation (pptx, pdf)

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

4. Two-variable linear programming

   • Incremental algorithm (pptx, pdf)

   • Randomized algorithm (pptx, pdf)

5. Voronoi diagrams and Delaunay triangulations

   • Voronoi diagram (pptx, pdf)

   • Plane sweep construction (pptx​​​​​​​, pdf)

   • Farthest-point Voronoi diagram (pptx, pdf)

   • Point set triangulation (pptx, pdf)

   • Delaunay triangulation (pptx, pdf)

   • Construction of Delaunay triangulation (pptx, pdf)

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

   • Discrepancy computation (pptx​​​​​​​, pdf)

   • Point-line duality (pptx, pdf)

   • Arrangement of lines (pptx, pdf)

   • Convex hulls in 3D (pptx​​​​​​​, pdf)

   • Envelopes, convex hulls and Voronoi diagrams (pptx, pdf)

7. Path planning 

   • Robot motion planning (pptx​​​​​​​, pdf)

   • Minkowski sum (pptx, pdf)

   • Visibility graphs and shortest paths (pptx​​​​​​​, pdf)