| Lect | Date | Topic | Reference |
| Geometric Fundamentals |
| 1 |
08/26 |
Introduction, models, geometric transforms |
[PS P.19-35] |
| Geometric Data Structures |
| 2 |
08/28 |
1D Data structures: segment and interval trees
|
[BCKO:5, 10] |
| 3 |
09/02 |
Orthogonal Range searching: quad tree, kd tree |
[BCKO:5] |
| 4 |
09/04 |
Orthogonal Range searching: kd tree, range tree |
[BCKO:5] |
| 5 |
09/09 |
Planar point location, persistent data structure |
[ST] |
| Intersection Detection |
| 6 |
09/11 |
Segment intersection: sweep-line, randomized incremental construction (RIC) |
[BCKO:2] |
| 7 |
09/16 |
Segment intersection: RIC analysis |
[BCKO:6] |
| Convex Hull |
| 8 |
09/18 |
2D convex hull |
[BCKO:1] |
| 9 |
09/23 |
Convex hull in high dimensions, duality |
[BCKO:11] |
| 10 |
09/25 |
Randomized incremental algorithm |
[BCKO:11] |
| Proximity Problems |
| 11 |
09/30 |
Voronoi Diagram, Delaunay Triangulation |
[BCKO:7] |
| 12 |
10/02 |
Randomized incremental algorithm |
[BCKO:9; Ed:9-17] |
| 13 |
10/07 |
Approximate NN searching |
[HP:2, 17] |
| 14 |
10/09 |
WSPD & its applications |
[HP:3] |
| 15 |
10/16 |
Geometric arrangements |
[HP:3; BCKO:8] |
| Geometric Sampling |
| 16 |
10/21 |
Random sampling, discrepancy, ε-approximations, ε-nets |
[HP:5] |
| 17 |
10//23 |
Geometric cutting |
[Ma:4] |
| 18 |
10/28 |
Simplex range searching |
[BCKO:16] |
| 19 |
10/30 |
Core sets, geometric summaries |
[HP:23] |
| Geometric Optimization |
| 20 |
11/04 |
Linear Programming (LP) |
[Cl] |
| 21 |
11/06 |
LP: Multiplicative Weight Method |
[AHK] |
| 22 |
11/11 |
Shape Similarity: Hausdorff, Frechet, DTW |
[AG] |
| 23 |
11/13 |
Shape Similarity: Optimal Transport |
[PC] |
| High Dimensional Geometry |
| 24 |
11/18 |
Low Distortion Embedding |
[Mat:15] |
| 25 |
11/20 |
Dimension Reduction |
[Mat:15] |
| 26 |
12/02 |
Locality Sensitive Hashing |
[HP:6] |