Computational Geometry

CS 498 TC, Spring 2021

Main  ❖  Syllabus  ❖  Schedule  ❖  Resources

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)