Tentative Schedule

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

Lec. Date Day Topic Notes
Aug 28 T No Class due to CSD IC
No Class
Aug 30 T No Class due to CSD IC
No Class
Sep 04 T No Class due to CSD IC
No Class
Sep 06 T No Class due to CSD IC
No Class
1 Sep 11 T Introduction, Sweep Line, and Line Intersection Problem
[ Introduction | Sweep Line | BKOS Chapter 2 | ClassNotes ]
2 Sep 13 T Point Location and Trapizodial Decomposition
[ BKOS Chapter 6 | ClassNotes ]
3 Sep 18 T Trapizodial Decomposition and Tail Estimates
[ BKOS Chapter 6 | ClassNotes | ClassNotes ]
4 Sep 20 T 2D LP and Backward Analysis
[ BKOS Chapter 4 | Brittany's ClassNotes ]
5 Sep 25 T Representing Topological Information
[ ClassNotes | Brisson | CMU Paper | Talk ]
6 Sep 27 T Geometric Transforms
[ Doru's Notes | ClassNotes ]
7 Oct 02 T Sorting, Convex Hull, and 2D Random Incremental Convex Hull
[ CH Intro | Class Notes]
8 Oct 04 T 2D Delaunay via Random Incremental Convex Hull
[ BKOS Chapter 9 | Class Notes]
HW1 out
9 Oct 09 T 2D Delaunay via Random Incremental continued plus upper bound theorem
[ BKOS Chapter 9 | Class Notes | Seidel's upper bd]
10 Oct 11 T Triangulated a Polygon
[ BKOS Chapter 3 | ClassNotes ]
11 Oct 16 T Triangulated a Polygon
[ BKOS Chapter 3 | ClassNotes ]
12 Oct 18 T Triangulated a PSLG Fast
[ Seidel Paper | ClassNotes ]
13 Oct 23 T Quadtree Meshing
[ Bern Eppstein Gilbert | ClassNotes ]
14 Oct 25 T Delaunay Refinemnt, Ruppert
[ Ruppert's 1995 Paper | ClassNotes ]
15 Oct 30 T Delaunay Refinemnt Lower Bounds
[ Mitchell Lower Bounds | Radius Edge Paper | ClassNotes ]
HW1 due
16 Nov 01 T Approximate Nearest Neighbor Search
[ Conference Paper | Journal Version | ClassNotes Part 1 | ClassNotes Part 1 ]
17 Nov 06 T Output Sensitive Delaunay Triangulation
[ ]
18 Nov 08 T Approximate Nearest Neighbor Search, Continued
[ ClassNotes ]
19 Nov 13 T Closest Pair and QT construction
[ HP Chap-1 | HP Chap-1 | ClassNotes ]
20 Nov 15 T Well Separated Pair Decomposition
[ HP Chap-3 | ClassNotes ]
21 Nov 20 T Convexifying a Polygon (Part 1)
[ Connelly Demaine and Rote | Connelly and Demaine | ClassNotes ]
Nov 22 T Thanksgiving no class
Thanksgiving
22 Nov 27 T Convexifying a Polygon (Part 2) and Graph Rigidity and Pseudo Triangulation
[ ClassNotes Part 2 ] Pseudo Triangulations Survey | Minimally Rigid Graphs | ClassNotes ]
23 Nov 29 T Quadtrees Via Z-orderings
[ Bern Eppstein Teng | ClassNotes ]
24 Dec 04 T Representing Curves
[ Chapter 3 | Chapter 4 | Chapter 5 | ClassNotes ]
25 Dec 06 T B-Splines
[ Chapter 8 | ClassNotes ]
26 Dec 11 T Recursive Subdivisions
[ Chapter 21 | Evaluation of Loop | ClassNotes ]
Possible Extra Classes
27 Dec 13 T Curve and Surface Reconstruction
[ TKD Chapter 2 | Amenta and Bern | ClassNotes ]
Possible Extra Classes
28 Dec 18 T Surface Reconstruction and Restricted Delaunay
[ Edelsbunner Shah ]
Possible Extra Classes
29 Dec 20 T
Possible Extra Classes