| Lect. | Date | Topics | Reading |
|---|---|---|---|
| 1 | Jan. 16 |
Introduction, Model of computation,
lower bounds | PS: Chapt. 1 |
| 2 | Jan. 21 |
Segment trees, interval trees,
priority-search trees segment intersection | PS: Sect. 1.2.3, 8.8
Meh: Sect. 5.1.2 PS: Sect. 7.2.3 |
| 3 | Jan. 28 |
Sweep-line algorithm, map overlay
Planar convex hulls: Graham scan, Jarvis march, on-line algorithm, optimal algorithms | PS: Sect. 7.2.3
PS: Chapter 3 |
| 4 | Feb. 4 |
Convex polytopes, duality
Convex hulls in higher dimensions | Ed Chapt 1
PS: Chapter 3 |
| 5 | Feb. 11 | Convex hulls: Randomized algorithm | Mul, Chapter 3 |
| 6 | Feb. 27 |
Segment intersection: Randomized algorithm
Diameter, width, normal diagram | Mul, Chapter 4
PS, Chapter 4 |
| 7 | March 4 |
Voronoi diagram: definition, properties, relationship with
convex hulls
Algorithms: randomized and deterministic | PS, Chapter 5
Mul, Chapter XX |
| 8 | March 6 |
Point location: slab method, persistent data structure
monotone chain method, fractional cascading | PS, Chapter 2 |
| 9 | March 25 |
Linear programming: algorithms in fixed dimensions;
Megiddo's 2d algorithm; Seidel's algorithm | PS, Chapter 7 |
| 10 | April 1 |
Linear programming: Clarkson's algorithm; LP-type problems
Parametric searching: slope selection | [AS96] |
| 11 | April 8 | Arrangements of lines and hyperplanes | Edels |
| 12 | April 10 |
Orthogonal range searching
Simplex range searching | PS, Chapte 2
[Mat] |
| 13 | April 15 |
Practical data structures: quadtree, kdtrees, bsp's
N-body problem | PS, Chapte 2 |
| 14 | April 22 | Ray tracing, hidden surface removal | |
| 15 | April 29 | Degneracies and robustness issues | [Hof89] |
Agarwal's Home Page