CS 498sh3: sp23 - Discrete & Computational
Geometry
- 4/25: Lecture 25: Planar separator.
- 4/18: Lecture 24: At most k level,
depth, etc.
- 4/13: Lecture 23: A spanning tree
with few crossings
- 4/11: Lecture 22: JL lemma
- 4/6: Lecture 21:
Measure concentration on
the sphere and JL lemma
- 4/4: Lecture 20: Brunn-Minkowski inequality
: The strange geometry of high dimensions.
- 3/28: Lecture 19: Perceptron algorithm
and variants.
- 3/23: Lecture 18: WSPD.
- 3/21: Lecture 17: Quadtrees.
- 3/9: Lecture 16: Union
complexity of pseudodisks.
- 3/7: Lecture 15: Motion
planning
- 3/2: Lecture 14: Interval
trees, Priority trees, and segment trees
- 2/28: Lecture 13: Delaunay
triangulations
- 2/23: Lecture 12: Voronoi diagrams
- 2/21: Lecture 11: Duality, inversion,
and polarity
- 2/16: Lecture 10: The moments technique,
and convex-hull in
three dimensions.
- 2/14: Lecture 9: Point location (Chapter 6 in the book).
- 2/9: Lecture 8: Orthogonal range searching.
- 2/7: Lecture 7: Closest pair.
- 2/2: Lecture 6: Low dimensions
linear programming
- 1/31: Lecture 5: Computing lowest
vertex above a set of lines.
- 1/26: Lecture 4: Triangulating a
simple polygon.
- 1/24: Lecture 3: Arrangements and planar graphs
- Planar graphs
- Arrangements
- 1/19: Lecture 2: Convexity
/ Sweeping.
- 1/17: Lecture 1: Introduction
& 2d Convex Hull
Last modified: Thu 2023-04-27 19:22:42 UTC 2023 by Sariel Har-Peled