Computational Geometry

CS 498 TC, Spring 2022

Main ❖ Syllabus ❖ Schedule ❖ Resources

---

• All future lecture topics and homework deadlines are tentative.
• I'm proving links to lecture scribbles and videos both from this semester and from Spring 2021. These do not always synchronize perfectly, but I'll provide the best match that I can.

🔐 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:

• Guarding a set of line segments in the plane
• Throwing a sofa through the window
• Counting nonomino tilings and other things of that ilk

Thu Apr 28

Homework 4 due 8pm

Fri Apr 29

🔐 Paper presentations:

• Stability of persistence diagrams
• From time series to complex networks: The visibility graph
• Computing Shapley values in the plane

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)

---