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 

2 
Sep 13 
T 
Point Location and Trapizodial Decomposition 

3 
Sep 18 
T 
Trapizodial Decomposition and Tail Estimates 

4 
Sep 20 
T 
2D LP and Backward Analysis 

5 
Sep 25 
T 
Representing Topological Information 

6 
Sep 27 
T 
Geometric Transforms 

7 
Oct 02 
T 
Sorting, Convex Hull, and 2D Random Incremental Convex Hull 

8 
Oct 04 
T 
2D Delaunay via Random Incremental Convex Hull 
HW1 out

9 
Oct 09 
T 
2D Delaunay via Random Incremental continued plus upper bound theorem 

10 
Oct 11 
T 
Triangulated a Polygon 

11 
Oct 16 
T 
Triangulated a Polygon 

12 
Oct 18 
T 
Triangulated a PSLG Fast 

13 
Oct 23 
T 
Quadtree Meshing 

14 
Oct 25 
T 
Delaunay Refinemnt, Ruppert 

15 
Oct 30 
T 
Delaunay Refinemnt Lower Bounds 
HW1 due

16 
Nov 01 
T 
Approximate Nearest Neighbor Search 

17 
Nov 06 
T 
Output Sensitive Delaunay Triangulation [ ]


18 
Nov 08 
T 
Approximate Nearest Neighbor Search, Continued 

19 
Nov 13 
T 
Closest Pair and QT construction 

20 
Nov 15 
T 
Well Separated Pair Decomposition 

21 
Nov 20 
T 
Convexifying a Polygon (Part 1) 


Nov 22 
T 
Thanksgiving no class 
Thanksgiving

22 
Nov 27 
T 
Convexifying a Polygon (Part 2) and Graph Rigidity and Pseudo Triangulation 

23 
Nov 29 
T 
Quadtrees Via Zorderings 

24 
Dec 04 
T 
Representing Curves 

25 
Dec 06 
T 
BSplines 

26 
Dec 11 
T 
Recursive Subdivisions 
Possible Extra Classes

27 
Dec 13 
T 
Curve and Surface Reconstruction 
Possible Extra Classes

28 
Dec 18 
T 
Surface Reconstruction and Restricted Delaunay 
Possible Extra Classes

29 
Dec 20 
T 

Possible Extra Classes
