Computational Geometry
- 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:
- 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
Reading day
- Wed May 11
- Final exam due 4:30pm (officially scheduled for 1:30â4:30)