Lectures

LectDateTopicReference
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]

top