CPS 234: Course Synopsis

  1. Models of computation and lower bound techniques: Various models of computation, algebraic decision trees, Ben-Or's theorem and its extensions.

  2. Algorithmic paradigms and geometric transforms: Divide and conquer, sweep-line, locus, duality, inversion.

  3. Storing and searching orthogonal objects: Segment tree, interval tree, range tree, priority search tree, quad tree, orthogonal range searching.

  4. Convex hulls: Planar convex hulls, Graham's scan, output-sensitive algorithms, dynamic algorithms, higher dimensional convex hulls, randomized algorithms, applications of convex hulls.

  5. Planar point location: Slab method, Kirkpatrick's algorithm, Sarnak-Tarjan algorithm, fractional cascading, point location in higher dimensions.

  6. Arrangements: Arrangements of lines, applications, sweep line algorithm, incremental algorithm, zone theorem, arrangements of hyperplanes and of simplices, lower envelope.

  7. Proximity problems: Closest pair, nearest neighbor, Voronoi diagram, generalized Voronoi diagrams.

  8. Linear programming: Megiddo's algorithm, randomized algorithms, parametric searching.

  9. Range searching: Half-plane range searching, Ham-Sandwich theorem, partition trees, epsilon-nets, lower bounds

  10. Motion planning: Configuration space, Minkowski sum, translational motion planning, shortest paths, nonholonomic motion planning.

  11. Graphics related problems: Hidden surface removal, binary space partition, ray tracing, surface simplification, n-body problem.

Agarwal's Home Page

CPS 234 Homepage.

Pankaj Kumar Agarwal
Fri Nov. 1 1996