CS 372 Computational Geometry

This course presents worst-case efficient algorithms for geometric problems. The main topics are: Notions of discrete geometry (convex hulls, planar graphs, triangulations, Delaunay graphs, Voronoi diagrams, arrangements of lines, point-line duality). Geometric algorithms design techniques (plane sweep, randomized incremental construction, bucketing, divide and conquer). Geometric data structures (doubly-connected edge list, history graphs, range trees, segment trees, and interval trees) Low-dimensional linear programming. Topological lower bounds. Implementation issues. These theoretical results are presented in connection with applications to computer graphics, robotics, databases, and geographic information systems.




CS 260