This course covers fundamental algorithms and data structures for convex hulls, Voronoi diagrams, Delauney triangulation, Euclidean spanning trees, point location, and range searching. Also included are lower bounds and discrepancy theory. Optimization in geometry will be covered. This includes fixed dimensional linear programming and shortest paths. Graphic data structures such as BSP trees will be covered.
[(CS 430 with min. grade of C)]