Computational Geometry

CS 498 TC, Spring 2022

Main    Syllabus    Schedule    Resources


🔐 Locks indicate content that is restricted to registered students (via university login credentials)

Polygons

Wed Jan 19
What is computational geometry?
Planar convex hulls: Jarvis' March (gift-wrapping)
[Mount 1–2, Swiss 4.3–4.5, Marks 1, Jeff's old notes]
[2022 scribbles] [2021 pre-scribbles, scribbles, video]
Fri Jan 21
More planar convex hulls: Graham's Scan (greedy local repair), Chan's algorithm (shattering)
[Mount 2, Swiss 4.6–4.8, Marks 1, Jeff's old notes]
[2022 scribbles, video] [2021 pre-scribbles, scribbles, video]
Wed Jan 26
Projective duality: Upper envelope of lines (merge-envelope and selection-envelope), new glasses
[Mount 6, Marks 8.2]
[2022 scribbles, video] [2021 pre-scribbles, scribbles, video]
Fri Jan 28
Segment intersection I: Plane sweep algorithm, detecting any intersections in $O(n\log n)$ time, finding all $k$ intersecting pairs in $O((n+k)\log n)$ time
[Mount 4, Marks 2, Swiss A]
[2022 scribbles, video] [2021 pre-scribbles, scribbles, video]
Wed Feb 2
Segment intersection II: finding all $I$ intersection points in $O((n+I)\log n)$ time
[Mount 4, Marks 2, Swiss A]
[2022 scribbles, video] [2021 pre-scribbles, scribbles, video]
Fri Feb 4
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)
[Mount 5, Marks 3, Swiss 3.2, Jeff's topology notes]
[2022 scribbles, video] [2021 scribbles, video]
Wed Feb 9
Point-in-polygon testing and winding numbers
[Jeff's topology notes on polygons and winding, Brushwood 2009, Maverick 2012]
[2022 scribbles, video] [2021 pre-scribbles, scribbles, video]
Thu Feb 10
Homework 1 due 8pm

Planar Maps

Fri Feb 11
Definitions (planar maps, planar straight-line graphs), data structures ("doubly-connected edge lists"), duality, Euler's formula
[Mount 10, Marks 2, Swiss 2, Jeff's topology notes, Eppstein 2018]
[2022 scribbles, video] [2021 pre-scribbles, scribbles, video]
Wed Feb 16
Euler's formula, randomized incremental construction
[Mount 8, Marks 6.2, Swiss C.3, ]
[2022 scribbles, video] [2021 pre-scribbles, scribbles, video]
Fri Feb 18
Randomized incremental analysis: conflict lists, history dags
[Mount 9, Marks 6.2, Swiss 9]
[2022 scribbles, video] [2021 pre-scribbles, scribbles, video]
Wed Feb 23
Point location via history dags, faster polygon triangulation
[Mount 9, Marks 6.2, Swiss 9, Seidel 1991]
[2022 scribbles, video] [2021 pre-scribbles, scribbles, video]
Thu Feb 24
Homework 2 due 8pm
Fri Feb 25
Voronoi diagrams and Delaunay triangulations
[Mount 11–12, Marks 7 and 9, Swiss 5 and 7]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, post-scribbles; video]
Tue Mar 1
Midterm due 8pm
Web Mar 2
Delaunay triangulations: Local=global, Lawson's flip algorithm, paraboloid lifting
[Mount 11–12, Marks 7 and 9, Swiss 5 and 7]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, video]
Fri Mar 4
Delaunay triangulations: Randomized incremental analysis
[Marks 9, Mount 12]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, video]
Wed Mar 9
Power diagrams, anti-Voronoi diagrams, and 3D convex hulls
[Wikipedia, Aurenhammer 1987, Edelsbrunner 2000]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, video]
Fri Mar 11
[cancelled]
Self-service drop deadline
Web Mar 16
Spring break
Fri Mar 18
Spring break

Optimization

Wed Mar 23
Linear programming background
[Swiss E, Marks 4, Mount 7, Jeff's notes]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, video]
Fri Mar 25
Fixed-dimensional kinear programming in $O(n)$ expected time
[Swiss F, Mount 7, Marks 4]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, video]
Wed Mar 30
Generalized LP: Smallest enclosing annuli and balls
[Swiss G, Marks 4.7]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, video]

Arrangements and Stuff

Fri Apr 1
Line arrangements: incremental construction and the zone theorem
[Mount 14, Marks 8, Swiss 8]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, video]
Wed Apr 6
Applications of line arrangements: discrepancy, ham sandwiches, and small triangles
[Mount 15, Marks 8, Swiss 8]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, video]
Fri Apr 8
Geometric shortest paths: The funnel algorithm
[Tompa 1981, Chazelle 1982, Lee and Preparata 1984; Jeff’s topology notes, Mulzer 2013]
[2022 scribbles, video]
[2021 scribbles, video]
Mon Apr 11
Homework 3 due 8pm
Wed Apr 13
Minkowski sums and motion planning
[Marks 13, Mount 34, Swiss D]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, sorry no video]
Fri Apr 15
Convolutions and Fréchet distance
[Convolutions: Wein 2006]
[Fréchet distance: Alt Godau 1995, Shäffer 2019, Fréchet View, van Dijk 2021 part 1, part 2, part 3]
[2022 scribbles, video]
[not covered in 2021]
Graduate drop deadline
Mon Apr 18
Presentation proposals due 8pm
Wed Apr 20
Fréchet and time warping distances
[Fréchet distance: Alt Godau 1995, Shäffer 2019, Fréchet View, van Dijk 2021 part 1, part 2, part 3]
[Time warping: White Neely 1976, Sakoe Chiba 1978, Kruskal Liberman 1983, Efrat Fan Venkatasubramanian 2006, Buchin Nusser Wong 2022 ]
[2022 scribbles, video]
[not covered in 2021]
Fri Apr 22
Visibility graphs
[Marks 15, Mount 24, Swiss 8.6; Pocchiola Vegter 1994]
[2022 scribbles, video]
[2021 pre-scribbles, scribbles, video]

What? Done already?

Wed Apr 27
🔐 Paper presentations:
Thu Apr 28
Homework 4 due 8pm
Fri Apr 29
🔐 Paper presentations:
Wed May 4
Cancelled; Jeff is traveling
Thu May 5
Last day to submit ICES evaluation forms
Reading day
Wed May 11
Final exam due 4:30pm (officially scheduled for 1:30–4:30)