Computational Geometry
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.
Polygons
- 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 constructions
- 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 algorithms
- 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
- [slack]
[TBA]
- Tue Mar 30
- [TBA]
- Thu Apr 1
- [TBA]
- Mon Apr 5
- Homework 4 due 8pm
- Tue Apr 6
- [TBA]
- Thu Apr 8
- [TBA]
- Tue Apr 13
- — No lecture — Spring break, Day 3
- Thu Apr 15
- [TBA]
- Mon Apr 19
- Homework 5 due 8pm
- Tue Apr 20
- [TBA]
- Thu Apr 22
- [TBA]
- Tue Apr 27
- [TBA]
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)