Tentative Schedule

This schedule is very preliminary: the number of lectures and order of the topics are likely to change.

Lec. Date Day Topic Instr. Reading
1 Jan 14 M Introduction and Convex Hulls BF BKOS Chapter 1
2 Jan 15 T Oriented Projective Geometry; Primitives BF Stolfi 87
3 Jan 18 F The Line Intersection Problem; Sweepline GM Class Notes | BKOS Chapter 2 Page 29
Jan 21 M Martin Luther King Day, No Class
4 Jan 23 W Graham Scan CH Algorithm BF BKOS Ch 2
5 Jan 25 F RIC for CH GM Class Notes | Lecture Notes
6 Jan 28 M Polygon Triangulations GM Class Notes | BKOS Ch 3
Jan 30 W Assignment 1 Presentations
7 Feb 01 F Arrangements BF BKOS Ch 8
8 Feb 04 M Halfplane Intersections BF BKOS Ch 4
9 Feb 06 W Planar Point Location; Trapezoidations I GM Class Notes | Mount Chap 9 | BKOS Ch 6
Feb 08 F Assignment 2 Presentations
10 Feb 11 M Planar Point Location; Trapezoidations II GM
11 Feb 13 W Voronoi Diagrams BF BKOS Sec 7.1
12 Feb 15 F Fortune's Algorithm BF BKOS Sec 7.2
13 Feb 18 M Geometric Transforms GM Class Notes
14 Feb 20 W Representing Topological Information GM Class Notes | Brisson-93
15 Feb 22 F QuadTrees and Mesh Generation GM Class Notes | BKOS Chap 14
Feb 25 M Assignment 3 Presentations
16 Feb 27 W Delaunay Triangulations BF BKOS Ch 9
17 Mar 01 F Closest Pair using Hashing GM Class Notes | Har-Peled Chap 1
18 Mar 04 M Delaunay Refinement GM Class Notes | Wikipedia Page
19 Mar 06 W Curves and Knots BF Sullivan
Mar 08 F Mid-Semester Break, No Class
Mar 11 M Spring Break, No Class
Mar 13 W Spring Break, No Class
Mar 15 F Spring Break, No Class
20 Mar 18 M Fréchet Distance I BF Godau 1991
21 Mar 20 W Fréchet Distance II BF Alt Godau '95
Mar 22 F Assignment 4 Presentations
22 Mar 25 M k-Centers and k-Medians I GM Har-Peled Chap 4
23 Mar 27 W k-Medians II GM
24 Mar 29 F Metrics BF
25 Apr 01 M Homology I BF Class Notes Hatcher 2.1
26 Apr 03 W Homology II BF
Apr 05 F Assignment 5 Presentations
27 Apr 08 M Shape of a Point Set I BF
28 Apr 10 W Shape of a Point Set II BF
29 Apr 12 F TBA BF
30 Apr 15 M Epsilon-Nets Part I GM Class Notes Har-Peled Chap-5
31 Apr 17 W Epsilon-samples and Epsilon-Nets Part II GM Har-Peled VC-notes
Apr 19 F Carnival, No Class
32 Apr 22 M Bezier Curves and Bossoms GM [Class Notes | CAGD Chap-3 | CAGD Chap-4 ]
33 Apr 24 W Subdivision Surfaces GM [Class Notes | Geri Pixar ]
34 Apr 26 F Approximate Nearest Neighbor GM [Class Notes | Har-Peled Chap 17 ]
35 Apr 29 M Brunn Minkowski inequality GM Har-Peled Chap 19 ]
36 May 01 W Johnson-Lindenstrauss Lemma GM Class Notes
37 May 03 F Assignment 6 Presentations
May 07 T Final: May 7 5:30-8:30pm: WEH 5310 Project Presentations