Computational Geometry
🔐 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 construction
[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)