Lectures

LectDateTopicReference
Geometric Fundamentals
1 08/28 Introduction, models, geometric transforms [PS P.19-35]
Geometric Data Structures I
2 08/30 1D Data structures: segment and interval trees [BCKO Ch5, 10]
3 09/04 Range searching: kd tree, quad tree [BCKO Ch5, 14]
4 09/06 Range searching: range tree [BCKO Ch5]
5 09/11 Planar point location [BCKO Ch6; ST]
Intersection Detection
6 09/13 Intersection detection: sweep-line, randomized incremental construction (RIC) [BCKO Ch2]
7 09/18 Intersection detection: RIC analysis [BCKO Ch6]
Convex Hull
8 09/20 2D convex hull [BCKO Ch1]
9 09/25 Convex hull in high dimensions [BCKO Ch11]
10 09/27 Randomized incremental algorithm [BCKO Ch11]
Proximity Problems
11 10/02 Voronoi diagram, Delaunay triangulation [BCKO Ch7]
12 10/04 RIC for DT, generalizations of DT [BCKO Ch9; Ed P.9-17]
13 10/11 Approximate NN searching [HP Ch2,17]
14 10/16 WSPD & its applications [HP Ch 3]
Arrangements
15 10/18 Arrangements of lines & curves [HP, Ch3; BCKO Ch 8]
16 10/23 Arrangements in higher dimensions [BCKO Ch8, Mat Ch 6,7, AS]
Geometric Sampling
17 10/25 Random sampling, e-nets, e-approximations [HP Ch5]
18 10/30 Core Sets [HP Ch23]
Geometric Optimization
19 11/01 Linear programming [HP Ch15]
20 11/06 Geometric set cover [HP Ch6]
21 11/08 Shape matching TBD
22 11/13 Clustering TBD
Geometric Data Structures II
23 11/15 Geometric cuttings [Ma Ch4&6]
24 11/20 Simplex range searching [BCKO Ch16]
High-dimensional geometry
25 11/27 Embedding techniques [Ma Ch15]
26 11/29 Locality sensitive hashing [HP Ch20]

Home