Computational Geometry

CS 498 TC, Spring 2021

Main    Syllabus    Schedule    Resources

All future topics are tentative. I have a much longer list of potential topics, from which I'll only have time to discuss a small minority.


Tue Jan 26
What is computational geometry?
Planar convex hulls: Jarvis' March (gift-wrapping)
[pre-scribbles, scribbles, video —  Mount 1–2, BGHW 4.3–4.5, BCKO 1, Jeff's old notes]
Thu Jan 28
More planar convex hulls: Graham's Scan (greedy local repair), Chan's algorithm (shattering)
[pre-scribbles, scribbles, video —  Mount 2, BGHW 4.6–4.8, BCKO 1, Jeff's old notes]
Tue Feb 2
Projective duality: Upper envelope of lines (merge-envelope and selection-envelope), new glasses
[pre-scribbles, scribbles, video —  Mount 6, BCKO 8.2]
Thu Feb 4
Segment intersection I: Detecting any intersections, plane sweep algorithm
[pre-scribbles, scribbles, video —  Mount 4, BCKO 2, BGHW A]
Tue Feb 9
Segment intersection II: Finding all $k$ intersecting pairs in $O((n+k)\log n)$ time, finding all $I$ intersection points in $O((n+I)\log n)$ time
[pre-scribbles, scribbles, video —  Mount 5, BCKO 2, BGHW A]
Thu Feb 11
Polygon triangulation: $O(n^2)$ time via diagonal divide-and-conquer; $O(n \log n)$ time via trapezoidal decompositions (plane sweep, boring diagonals, monotone mountains)
[scribbles, video —  Mount 4, BCKO 3, BGHW 3.2, Jeff's topology notes]
Mon Feb 15
Homework 1 due 8pm
Tue Feb 16
— no lecture —
Wed Feb 17
Spring break, Day 1
Thu Feb 18
Point-in-polygon testing and winding numbers

[ pre-scribbles, scribbles, video —  Jeff's topology notes on polygons and winding, Brushwood 2009, Maverick 2012]

Planar Maps

Tue Feb 23
Definitions, data structures, and Euler's formula
Thu Feb 25
Trapezoidal decompositions: Plane sweep (again) and randomized incremental con­struc­tions
Mon Mar 1
Homework 2 due 8pm
Tue Mar 2
Point location (randomized incremental history)
Thu Mar 4
Polygon triangulation redux
Mon Mar 8
Midterm due 10pm
Tue Mar 9
Voronoi diagrams, Delaunay triangulations, and 3d convex hulls
Thu Mar 11
Voronoi / Delaunay algo­rithms
Tue Mar 16
More Voronoi / Delaunay algorithms (Beyond the Planet of the Convex Hulls)
Thu Mar 18
Voronoi / Delaunay applications: Interpolation, post-office problem
Mon Mar 22
Homework 3 due 8pm
Tue Mar 23
— No lecture —
Wed Mar 24
Spring break, day 2
Thu Mar 25


Tue Mar 30
Thu Apr 1
Mon Apr 5
Homework 4 due 8pm
Tue Apr 6
Thu Apr 8
Tue Apr 13
— No lecture — Spring break, Day 3
Thu Apr 15
Mon Apr 19
Homework 5 due 8pm
Tue Apr 20
Thu Apr 22
Tue Apr 27

What? Done already?

Thu Apr 29
Paper presentations
Tue May 4
Paper presentations / review / something new
Wed May 5
Drop deadline
Thu May 6
Reading day
Mon May 10
Final exam due 10pm (officially scheduled for 8-11am)