Computational Geometry
Brain Dump
This is just a brainstorming list, with an attempted resolution of one lecture per bullet. Don't take ordering too seriously. There are a total of 28 class periods in the schedule. If I allocate one for the midterm, two for Wednesday instructional breaks, and one for student presentations, that leaves room for 24 lectures. Ha ha yeah right.
- Models of computation: and models
- Real RAM
- Algebraic decision trees
- ($k$)-linear decision trees
- Algebraic computation trees
- Ben-Or's $\Omega(n\log n)$ element distinctness lower bound
- Basic primitives
- orientation (cw/ccw)
- segment intersection
- incircle
- 3d orientation
- linearization?
- symnbolic perturbation
- Point in polygon, winding number
- Planar convex hulls:
- Gift-wrapping / Jarvis march
- Graham scan / Dreigroschenverfarhen
- Divide and conquer: quickhull and mergehull
- Prune and search: quickhull
- Chan's shatter-hull
- Randomized incremental
- Simple polygons
- Rotating calipers (diameter)
- Higher-dimensional convex hulls:
- Gift-wrapping (rocket algorithm)
- Randomized incremental
- Line segment intersection (sweep line)
- Detection (polygon simplicity)
- Reporting
- (Degeneracy: Report intersection points, not pairs)
- Trapezoidal decomposition
- Construction via sweeping
- Randomized incremental construction
- Data structures for planar maps
- Polygon intersection
- Cylindrical decomposition = (Persistent kinetic)$^d$ binary trees
- Polygon triangulation
- Dehn--Lannes algorithm
- Monotone mountains in $O(n)$ time
- Reduction to monotone mountains via trapezoidal decomposition
- Clarkson/Devillers/Seidel randomized $O(n\log^* n)$ time
- Application: Art gallery problem
- Application: Minkowski sums/convolution
- Point location
- Point in polygon again
- Sweep + persistence (line segments)
- Randomized incremental (line segments, Delaunay, Voronoi)
- Dobkin-Kirkpatrick hierarchy
- Adamy-Seidel
- Shortest paths and ray shooting
- Funnel algorithm
- Geodesic pseudotriangulation
- Visibility graphs
- BSP trees
- Definitions
- Ray shooting
- Painter's algorithm
- CSG
- 2d randomized incremental construction
- 3d randomized incremental construction
- Seidel and Chazelle lower bounds
- Line arrangements
- projective duality (relate to convex hulls)
- $O(n^2\log n)$ line sweep
- Zone Theorem
- $O(n^2)$ incremental
- Sylvester-Gallai theorem
- Minimum-area triangle
- Ham-sandwich theorem
- 3SUM-hardness
- Gajentaan–Overmars: degeneracy detection, polygon union, motion planning, etc.
- Adversary lower bound $\to$ 3-linear decision trees
- Grønlund–Pettie: $O(n^{3/2})$-depth 4-LDTs
- Kane—Lovett—Moran: $O(n\log^2 n)$-depth 6-LDTs
- Voronoi + Delauany
- Definitions
- Planar duality
- Data structures again
- Lawson's flip algorithm
- Lawson termination: paraboloid lifting
- Randomized incremental
- Fortune's algorithm (sketch only!)
- Optimality (max min angle, Raman's criteria, MST)
- Weighted (coherent/power) diagrams
- Fixed-dimensional linear programming
- Determinisic ($d\le 3$)
- Seidel randomized
- Welzl's minidisk algorithm (LP-type problems)
- Multiplicative weight updates ("Swiss algorithm")
- Orthogonal range searching
- 1d range trees
- Segment trees
- Interval trees
- Priority search trees
- Multilevel: rectangular range queries, orthogonal segment stabbing, rectangle stabbing
- Fractional cascading
- Quadtrees + Octtrees
- Maxwell–Cremona correspondence
- Tutte spring embedding
- Equilibrium stresses and force diagrams
- equilibrium stress $\leftrightarrow$ reciprocal diagram
- polyhedral lift $\leftrightarrow$ reciprocal diagram
- Rigidity (LP dual to equilibrium)
- Carpenter's rule theorem
- Pointed pseudotriangulations
- Resolving loads (Rote-Schulz)
- Well-separated pair decompositions
- All nearest neighbors
- $n$-body simulation
- EMST
- Simplex range searching (oof)
- Kinetic data structures
- Delaunay/Voronoi
- 2d convex hulls
- Collision detection
- Fréchet distance (and variants)
- Circular
- SETH-conditional lower bounds
- Translational motion planning
- Configuration spaces
- Minkoswki sums and convolution