Introduction to Computational Geometry (COMS 4180/5180)

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 (gb.pptx, gb.pdf)

   • Convex hulls in 2D (cv.pptx, cv.pdf)

   • Line segment intersection (lsi.pptx, lsi.pdf)

2. Geometric data structures and queries

   • Doubly-connected edge list (dcel.pptx, dcel.pdf)

   • Kd-trees (kd.pptx, kd.pdf)

   • Range trees (rt.pptx, rt.pdf)

   • Point location (loc.pptx, loc.pdf)

   • Trapezoidal maps (tm.pptx, tm.pdf)

   • Interval trees (it.pptx, it.pdf)

   • Priority search trees (pst.pptx, pst.pdf)

   • Segment trees (st.pptx, st.pdf)

   • Quadtrees (qt.pptx, qt.pdf)

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

   • Overlay of two subdivisions (overlay.pptx, overlay.pdf)

   • The Art Gallery problem (gallery.pptx, gallery.pdf)

   • Polygon triangulation (poly-trian.pptx, poly-trian.pdf)

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

4. Two-variable linear programming

   • Incremental algorithm (lp-incre.pptx, lp-incre.pdf)

   • Randomized algorithm (lp-random.pptx, lp-random.pdf)

5. Voronoi diagrams and Delaunay triangulations

   • Voronoi diagram (vor.pptx, vor.pdf)

   • Plane sweep construction (vor-sweep.pptx​​​​​​​, vor-sweep.pdf)

   • Farthest-point Voronoi diagram (fpvd.pptx, fpvd.pdf)

   • Point set triangulation (pt-trian.pptx, pt-trian.pdf)

   • Delaunay triangulation (del-trian.pptx, del-trian.pdf)

   • Construction of Delaunay triangulation (del-trian-constr.pptx, del-trian-constr.pdf)

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

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

   • Point-line duality (dual.pptx, dual.pdf)

   • Arrangement of lines (arrange.pptx, arrange.pdf)

   • Convex hulls in 3D (cv-3d.pptx​​​​​​​, cv-3d.pdf)

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

7. Path planning 

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

   • Minkowski sum (mink-sum.pptx, mink-sum.pdf)

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