Skip to main content

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 (pptx, pdf)
    • The Art Galley problem (pptx, pdf)
    • Polygon triangulation (pptx, pdf)
    • Half-plane intersection (pptx, pdf)
  4. Two-variable linear programming
  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)