| Lect | Date | Topic | Reference |
| Geometric Fundamentals |
| 1 |
1/06 |
Introduction, models, geometric transforms |
[PS P.19-35] |
| Geometric Data Structures I |
| 2 |
1/11 |
1D Data structures: segment and interval trees
|
[BCKO Ch5, 10] |
| 3 |
1/13 |
Orthogonal Range searching: quad tree, kd tree |
[BCKO Ch5] |
| 4 |
1/18 |
Range searching: kd tree, range tree |
[BCKO Ch5] |
| 5 |
1/20 |
Planar point location, persistent data structure |
[BCKO Ch6; ST] |
| Intersection Detection |
| 6 |
1/25 |
Intersection detection: sweep-line, randomized incremental construction (RIC) |
[BCKO Ch2] |
| 7 |
1/27 |
Intersection detection: RIC analysis |
[BCKO Ch6] |
| Convex Hull |
| 8 |
2/01 |
2D convex hull |
[BCKO Ch1] |
| 9 |
2/03 |
Convex hull in high dimensions |
[BCKO Ch11] |
| 10 |
2/08 |
Dynamic convex hull |
[PS Ch3] |
| Proximity Problems |
| 11 |
2/10 |
Voronoi diagram, Delaunay triangulation |
[BCKO Ch7] |
| 12 |
2/15 |
Randomized incremental and edge-flip algorithms for DT |
[BCKO Ch9; Ed P.9-17] |
| 13 |
2/17 |
Approximate NN searching |
[HP Ch2,17] |
| 14 |
2/22 |
WSPD & its applications |
[HP Ch 3] |
| Arrangements |
| 15 |
2/24 |
Arrangements of planar objects |
[HP, Ch3; BCKO Ch 8] |
| 16 |
3/01 |
Motion Planning |
[BCKO Ch13] |
| Geometric Sampling |
| 17 |
3/03 |
Random sampling, e-nets, e-approximations |
[HP Ch5] |
| 18 |
3/15 |
Core Sets, geometric summaries |
[HP Ch23] |
| Geometric Data Structures II |
| 19 |
3/17 |
Geometric cuttings & Polynomial Partitioning |
[HP Ch15] |
| 20 |
3/22 |
Simplex range searching & Beyond |
[HP Ch6] |
| Geometric Optimization |
| 21 |
3/24 |
Linear programming |
[CL, MSW] |
| 22 |
3/29 |
Geometric Hitting Set & Set Cover |
[HP Ch6, BG] |
| 23 |
3/31 |
Shape matching |
[MA Ch4,6] |
| 24 |
4/05 |
Clustering |
[BCKO Ch16] |
| Dimension Reduction |
| 25 |
4/07 |
Low distortion embeddings |
[Ma Ch15] |
| 26 |
4/12 |
Locality sensitive hashing |
[HP Ch20] |
