Lectures

LectDateTopicReference
Geometric Fundamentals
1 01/09 Introduction, models, geometric transforms [PS P.19-35]
Geometric Data Structures I
2 01/14 1D Data structures: segment and interval trees [BCKO Ch5, 10]
3 01/16 2D Orthogonal range searching: kd tree, range tree [BCKO Ch5; GO Ch36]
4 01/21 Planar point location [BCKO Ch6; ST]
Intersection Detection
5 01/23 Intersection detection: sweep-line, randomized incremental construction (RIC) [BCKO Ch2]
6 01/28 RIC analysis [BCKO Ch6]
Convex Hull
7 01/30 2D Convex Hull, convex polytopes, diameter, width [PS Ch3; BCKO Ch1; Ma Ch5]
8 02/04 Convex hull in high dimensions [PS Ch3; BCKO Ch11]
Proximity Problems
9 02/06 Voronoi diagram, Delaunay triangulation [BCKO Ch7]
10 02/11 RIC for DT, generalizations of DT [BCKO Ch9; Ed P.9-17]
11 02/13 [Cancelled] Approximate NN searching
12 02/18 WSPD & its applications [HP Ch 3,11]
Arrangements
13 02/20 WSPD, Arrangements [HP, Ch3; BCKO Ch 8]
14 02/25 Arrangements [BCKO Ch8, Mat Ch 6,7, AS]
Triangulations
15 02/27 Minimum-weight triangulation, Delaunay refinement [Ed Ch2]
16 03/06 Mesh simplification [Ed Ch4, GH]
Geometric Sampling
17 03/18 Random sampling, e-nets, e-approximations [HP Ch5]
18 03/20 Geometric summaries, core sets [HP Ch23; AHV]
Geometric Data Structures II
19 03/25 Geometric cuttings [Ma Ch 4 & 6]
20 03/27 Simplex range searching [BCKO Ch16; AE]
Geometric Optimization
21 04/01 Linear programming [HP Ch15; Cla]
22 04/03 Geometric set cover [HP Ch6; BG]
23 04/08 Shape matching [SU Ch3]
24 04/10 Clustering
Dimension Reduction
25 04/15 Embedding techniques [Ma Ch15]
26 04/17 Nearest Neighbor Searching [HP Ch20]
27 04/22 Locality sensitive hashing [HP Ch20]

top