Lect | Date | Topic | Reference |
Geometric Fundamentals |
1 |
01/14 |
Introduction, models, geometric transforms |
[PS P.19-35] |
Geometric Data Structures I |
2 |
01/19 |
1D Data structures: segment and interval trees
|
[BCKO Ch5, 10] |
3 |
01/21 |
2D Orthogonal range searching: kd tree, range tree |
[BCKO Ch5; GO Ch36] |
4 |
01/26 |
Planar point location |
[BCKO Ch6; ST] |
Intersection Detection |
5 |
01/28 |
Intersection detection: sweep-line, randomized incremental construction (RIC) |
[BCKO Ch2] |
6 |
02/02 |
RIC analysis |
[BCKO Ch6] |
Convex Hull |
7 |
02/04 |
2D convex hull |
[PS Ch3; BCKO Ch1; Ma Ch5] |
8 |
02/09 |
Convex hull in high dimensions |
[PS Ch3; BCKO Ch11] |
9 |
02/11 |
Randomized incremental algorithm |
[BCKO Ch11] |
Proximity Problems |
10 |
02/16 |
Voronoi diagram, Delaunay triangulation |
[BCKO Ch7] |
11 |
02/18 |
RIC for DT, generalizations of DT |
[BCKO Ch9; Ed P.9-17] |
12 |
02/23 |
Approximate NN searching |
[HP Ch2,17] |
13 |
02/25 |
WSPD & its applications |
[HP Ch 3] |
Arrangements |
14 |
03/01 |
Arrangements of lines & curves |
[HP, Ch3; BCKO Ch 8] |
15 |
03/03 |
Arrangements in higher dimensions |
[BCKO Ch8, Mat Ch 6,7, AS] |
Geometric Data Structures II |
16 |
03/08 |
Random sampling, e-nets, e-approximations |
[HP Ch5] |
17 |
03/10 |
Geometric cuttings |
[Ma Ch 4 & 6] |
18 |
03/29 |
Simplex range searching |
[BCKO Ch16; AE] |
19 |
03/31 |
Geometric summaries, core sets |
[HP Ch23; AHV] |
20 |
04/05 |
Linear sketches |
[AMS; Cor] |
Geometric Optimization |
21 |
04/07 |
Linear programming |
[HP Ch15; Cla] |
22 |
04/12 |
Geometric set cover |
[HP Ch6; BG] |
23 |
04/14 |
Shape matching |
[SU Ch3] |
24 |
04/10 |
Euclidean TSP |
[HP CH13] |
Dimension Reduction |
25 |
04/21 |
Embedding techniques |
[Ma Ch15] |
26 |
04/26 |
Locality sensitive hashing |
[HP Ch20] |