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
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
22 Nov 27 T Convexifying a Polygon (Part 2) and Graph Rigidity and Pseudo Triangulation
23 Nov 29 T Quadtrees Via Z-orderings
24 Dec 04 T Representing Curves
25 Dec 06 T B-Splines
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