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.