| Date | Topic | Scribe | Notes
|
| Fundamental Geometric Structures
|
| Jan 9 | Convex Hulls in 2D. Jarvis March and Graham Scan | SV |
|
| Jan 11 | Convex Hulls in 2D continued. 3D Hulls. The Upper Bound Theorem | SV | Assignment 1 (due 1/23; tex source and style file)
|
| Jan 16 | Duality and arrangements. Zone Theorem. | Harsh Doshi | [CGAA Chap. 8]
|
| Jan 18 | Voronoi Diagrams | Samuel Baird | [CGAA Chap 7]. A beautiful applet that demonstrates Fortune's algorithm step by step.
|
| Jan 23 | Delaunay Triangulations | Carson Brownlee | [CGAA Chap. 9]. Delaunay applet. Assignment 2 (due Feb 8; tex)
|
| Jan 25 | Delaunay Triangulations (cont.) | Linh Ha |
|
| Geometric Searching
|
| Jan 30 | No class | |
|
| Feb 1 | Point Location, Trapezoidal Decompositions and Triangulations | Brandon Hoff | [CGAA Chap. 6]
|
| Feb 6 | 1D/2D Range Searching, Kd trees | Thiago Ize | [CGAA Chap. 5]
|
| Feb 8 | Quad trees, interval trees, segment trees | Patrick Kelly | [CGAA Chap. 10]
|
| Feb 13 | Abstract Range Searching | David Koop | Geometric Range Searching (Agarwal/Erickson)/Assignment 3 (due Feb 27; .tex).
|
| Geometric Optimization
|
| Feb 15 | LPs: basics | Benjamin Mabey | Ch. 7 from Theory of Linear and Integer Programming, by Schrijver (amazon.com), Chapter 7 scanned
|
| Feb 20 | Computing fixed-dimensional LPs | John-Paul Ownby | A brief history of linear programming (first two pages), Megiddo's linear time algorithm in 2d (and 3d)
|
| Feb 22 | Seidel's Randomized Incremental Construction, and a simple LP construction | Pankaj Nathani | [CGAA Chap. 4], Kleinberg/Tardos(Chapter 11.6), Seidel's Algorithm
|
| Feb 27 | No class: Snow day | |
|
| Mar 1 | Clustering (1-center and k-center) | Blake Nelson | [CGAA Chap. 4], Gonzalez' k-center algorithm.
|
| Path Planning
|
| Mar 6 | Computing Minkowski Sums | Piyush Rai | [CGAA Chap. 13]
|
| Mar 8 | Shortest paths using visibility graphs | Chelsea Robertson | [CGAA Chap. 15]
|
| Models and Lower Bounds
|
| Mar 13 | Lower bounds for geometric problems; decision trees, algebraic decision trees and algebraic computation trees | Austin Robison | Jeff Erickson's lecture notes
|
| Mar 15 | The problem of the floor function; 3SUM-hardness | Mathias Schott | Encoding SAT using arithmetic on the RAM, 3SUM survey by Gajentaan and Overmars
|
| Mar 27 | NO CLASS TODAY (Suresh is travelling) | |
|
| Mar 29 | Grad Admit Prep (No class) | |
|
| Geometric Approximations
|
| Apr 3 | Sick day :( | |
|
| Apr 5 | Randomization Primer | Jianrong Shu | Probability and Computing (Mitzenmacher/Upfal) [Ch 3/4]: amzn/utah lib
|
| Apr 10 | The Johnson-Lindenstrauss Lemma | Huy Vo | Matousek Ch. 15.1, Dasgupta/Gupta
|
| Apr 12 | Approx Nearest Neighbour (high D) | Brian Young | Notes on ANN in hi-D, LSH web page (with code)
|
| Apr 17 | VC dimension | SV | Matousek Ch 10 (library), Notes on VC-dimension
|
| Apr 19 | Epsilon nets | SV | Matousek Ch 10 (library), Notes on VC-dimension
|
| Apr 24 | Wrap up: Simplex Range Searching and Cuttings, Dynamic CG, Core Sets, Computational Topology and Theories of Shape, Combinatorial Geometry, Art Gallery Problems, Streaming Geometry, | SV |
|
| Apr 26 | NO CLASS: Organick lecture | |
|
| May 1 | | |
|
| May 3 | | |
|
