Computational Geometry

CS 498 TC, Spring 2021

Main    Syllabus    Schedule    Resources


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

Polygons

Tue Jan 26
What is computational geometry?
Planar convex hulls: Jarvis' March (gift-wrapping)
[pre-scribbles, scribbles, video —  Mount 1–2, Swiss 4.3–4.5, Marks 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, Swiss 4.6–4.8, Marks 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, Marks 8.2]
Thu Feb 4
Segment intersection I: Detecting any intersections, plane sweep algorithm
[pre-scribbles, scribbles, video —  Mount 4, Marks 2, Swiss 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 4, Marks 2, Swiss 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 5, Marks 3, Swiss 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 (planar maps, planar straight-line graphs), data structures ("doubly-connected edge lists"), duality
[pre-scribbles, scribbles, video —  Mount 10, Marks 2, Swiss 2, Jeff's topology notes]
Thu Feb 25
Euler's formula, plane sweep bookkeeping, randomized incremental con­struc­tion
[pre-scribbles, scribbles, video —  Mount 8, Marks 6.2, Swiss C.3, Eppstein 2018]
Mon Mar 1
Homework 2 due 8pm
Tue Mar 2
Randomized incremental analysis: conflict lists, history dags
[pre-scribbles, scribbles, video —  Mount 9, Marks 6.2, Swiss 9]
Thu Mar 4
Point location via history dags, faster polygon triangulation
[pre-scribbles, scribbles, video —  Mount 9, Marks 6.2, Swiss 9, Seidel 1991]
Mon Mar 8
Midterm due 10pm
Tue Mar 9
Voronoi diagrams and Delaunay triangulations
[pre-scribbles, scribbles, post-scribbles; video (started late), video (rerecorded later) —  Mount 11–12, Marks 7 and 9, Swiss 5 and 7]
Thu Mar 11
Delaunay triangulations: Local=global, Lawson's flip algorithm, paraboloid lifting
[pre-scribbles, scribbles, video —  Mount 11–12, Marks 7 and 9, Swiss 5 and 7]
Tue Mar 16
Delaunay triangulations: Randomized incremental analysis
[pre-scribbles, scribbles, video —  Marks 9, Mount 12]
Thu Mar 18
Power diagrams, anti-Voronoi diagrams, and 3D convex hulls
[pre-scribbles, scribbles, video —  Wikipedia, Aurenhammer 1987, Edelsbrunner 2000]
Tue Mar 23
— No lecture —
Wed Mar 24
Spring break, day 2

Optimization

Thu Mar 25
Linear programming background
[pre-scribbles, scribbles, video —  Swiss E, Marks 4, Mount 7]
Mon Mar 29
Homework 3 due 8pm
Tue Mar 30
Fixed-dimensional kinear programming in $O(n)$ expected time
[pre-scribbles, scribbles, video —  Swiss F, Mount 7, Marks 4]
Thu Apr 1
Generalized LP: Smallest enclosing balls
[pre-scribbles, scribbles, video —  Swiss G, Marks 4.7]

Arrangements and Stuff

Tue Apr 6
Line arrangements: incremental construction and the zone theorem
[pre-scribbles, scribbles, video —  Mount 14, Marks 8, Swiss 8]
Thu Apr 8
— Cancelled — (vaccination recovery)
Tue Apr 13
— No lecture — Spring break, Day 3
Wed Apr 14
Homework 4 due 8pm
Thu Apr 15
Applications of line arrangements: discrepancy, ham sandwiches, and small triangles
[pre-scribbles, scribbles, video —  Mount 15, Marks 8, Swiss 8]
Fri Apr 16
Presentation proposals due
Tue Apr 20
Geometric shortest paths: The funnel algorithm
[scribbles, video — Tompa 1981, Chazelle 1982, Lee and Preparata 1984 — Jeff’s topology notes, Mulzer 2013] ]
Thu Apr 22
Minkowski sums and motion planning
[pre-scribbles, scribbles, video* — Marks 13, Mount 34, Swiss D; Wein 2006]
(*Sorry, I forgot to record the live lecture.)
Tue Apr 27
Visibility graphs
[pre-scribbles, scribbles, video — Marks 15, Mount 24, Swiss 8.6; Pocchiola Vegter 1994]
Wed Apr 27
Homework 5 due 8pm

What? Done already?

Thu Apr 29
Paper presentations 🔐
Tue May 4
Paper presentations 🔐
Wed May 5
Drop deadline
Thu May 6
Last day to submit ICES evaluation forms
Reading day
Mon May 10
Final exam due 10pm (officially scheduled for 8-11am)