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, 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, geographic information systems.
Course period09/3/11 → …
Course level300