22905 Computational Geometry
Credits: 4 graduate credits in Computer Science
Prerequisite: Admission to the graduate program in Computer Science 1
The course is based on chapters from Computational Geometry: Algorithms and Applications (3rd ed.), by M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars (Springer-Verlag, 2008).
Computational geometry deals with the design and analysis of algorithms for solving geometrical problems. This field is rooted in classical Mathematics and is related to both theoretical computer science and practical applications. It deals with problems relating to geometrical objects (such as points, lines, planes, line segments, and other geometric entities) in both low dimensional and high dimensional Euclidean space. Theoretical research in computational geometry is applied in additional areas of Computer Science (CS) such as computer vision, computer graphics and robotics, as well as in non-CS fields such as Engineering, Statistics, and Molecular Biology.
The course acquaints students with classical problems of computational geometry, methods for analyzing them and various up-to-date algorithmic techniques for solving them. It discusses a wide range of problems such as line segment intersections, computing convex hulls in the plane and in higher dimensions, Voronoi diagrams, triangulations, low-dimensional linear programming, geometry of rectangles, segment trees, point location, arrangements in the plane, randomized algorithms, and robot motion planning.
1Students who have not fulfilled this requirement may, under certain circumstances, enroll in this course.