Computational Geometry

3 units

Computational geometry is the algorithmic study of problems that involve geometric shapes such as points, lines, and polygons. Such problems appear in computer graphics, vision, robotics, animation, visualization, molecular biology, and geographic information systems. This course covers data structures that are unique to geometric computing, such as convex hull, Voronoi diagram, Delaunay triangulation, arrangement, range searching, KD-trees, and segment trees. Also covered are algorithms for polygon triangulation, path planning, and the art gallery problem.