CS529-Fall '07. WHAT TO READ BEFORE CLASS

The following entries show what I intend to cover during certain classes.
If you try to read this material in advance, it should make it easier to follow
the class. After the class, I will update the entry to reflect what was actually covered.

1. Sept. 6, 2007: Introduction, Bisecting diameter prob, Start convex hulls in the plane: left-turn primitive; Jarvis-march; expected number of hull edges in Conv(S) for n random points.

2. Sept 14, 2007: (makeup 1 for missed class 9/13) Maxima in point sets in the plane; the expected number for a random sample from the square. Lower bound for structured convex hull in the plane. Grahams (optimal) planar hull algorithm. Begin Quickhull.

3. Sept 20, 2007: Finish Quickhull. Planar divide-and-conquer hull algorithm. Incremental hull algorithm; pyramidal update. Randomized incremental algorithm and "backward analysis". Kirkpatrick-Seidel output-sensitive hull algorithm. Remaining 2-dim hull issues. Begin lower bounds via connected components.

4. September 27, 2007: Element uniqueness problem: lower bound by connected components argument. Dobkin-Lipton theorem. Some examples. Ben-Or's Theorem for algebraic decision trees, the lower bound for the unstructured convex hull problem in the plane.

5. October 4, 2007: Complete lower bound proof. The segment intersection problem (Chapter 2 of the Dutch book) and the plane-sweep algorithm for it.

6. October 11, 2007: Planar embeddings and datastructures for them. Planar graphs and Eulers Theorem. The art gallery theorem. Triangulations of a simple polygon and Fisks proof. Begin algorithms for polygon triangulation.

7. October 18, 2007: Jihui Zhao talked about k-d trees, range searching, and fractional cascading.

8. October 25, 2008: Triangulating simple polygons in O(n log(n)): (i) triangulating a monotone polygon in O(n) time; (ii) partitioning a simple polygon into the union of cn x-monotone polygons via an O(n log(n)) sweepline algorithm.

9. November 1, 2007: Point location in planar maps. The slab method. The trapezoidal decomposition and the randomized, incremental algorithm to construct it, along with the point-location data structure.

10. November 8, 2007: Finish the point location data-structure. Begin duality and arrangements - example 1: slope selection.

11. November 9, 2007: (makeup class 5-6:20PM in Hill 120) Continue with levels in arrangements and the existence of ham-sandwich cuts. Megiddo's linear time algorithm for the separated case.

12. November 15, 2007: Edelsbrunner-Waupotitsch O((m+n)log(m+n)) alg for the general case. Begin linear programming in the plane and the solution by halfspace intersection in O(n log(n)) [this is optimal for computation of the intersection of halfspaces.

13. November 29, 2007: Megiddo's O(n) algorithm for LP in the plane. Linear separability and other applications of LP. Begin arrangements and their construction. The zone theorem. Applications.

14. November 30, 2007 (Makeup): O(n^2) alg to construct a DCEL for the arrangement of n given lines; zone thm justifies the analysis of the alg. Begin parametric search, exemplified by the problem of slope selection.

15. December 6, 2007: Finish parametric search and its application to slope selection - this gives an O(n(log n)^2) alg for this problem. Begin Voronoi diagram in the plane.