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 
    • Geometric basics (pdf)
    • Convex hulls in 2D (pdf)
    • Line segment intersection (pdf)
  2. Geometric data structures and queries
    • Doubly-connected edge list (pdf)
    • Kd-trees (pdf)
    • Range trees (pdf)
    • Point location (pdf)
    • Trapezoidal maps (pdf)
    • Interval trees (pdf)
    • Priority search trees (pdf)
    • Segment trees (pdf)
    • Quadtrees (pdf)
  3. Overlay, polygon triangulation, and half-plane intersection
    • Overlay of two subdivisions (pdf)
    • The Art Gallery problem (pdf)
    • Polygon triangulation (pdf)
    • Half-plane intersection (pdf)
  4. Two-variable linear programming
    • Incremental algorithm (pdf)
    • Randomized algorithm (pdf)
  5. Voronoi diagrams and Delaunay triangulations
    • Voronoi diagram (pdf)
    • Plane sweep construction (pdf)
    • Farthest-point Voronoi diagram (pdf)
    • Point set triangulation (pdf)
    • Delaunay triangulation (pdf)
    • Construction of Delaunay triangulation (pdf)
  6. Duality, line arrangements, convex hulls, and envelopes
    • Discrepancy computation (pdf)
    • Point-line duality (pdf)
    • Arrangement of lines (pdf)
    • Convex hulls in 3D (pdf)
    • Envelopes, convex hulls and Voronoi diagrams (pdf)
  7. Path planning 
    • Robot motion planning (pdf)
    • Minkowski sum (pdf)
    • Visibility graphs and shortest paths (pdf)