# 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]
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: 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]
Mon Apr 18
Presentation proposals due 8pm
Wed Apr 20
[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]

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