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.