Computational Geometry

Computational geometry considers problems with geometric input, and its goal is to design efficient algorithms and to study the computational complexity of such problems. A typical input to a problem is some set of points or segments in the Euclidean plane (or higher dimensional Euclidean space). Examples of problems include computing the convex hull of the point set, finding clusters, or setting up a data structure to find the nearest point to a given query point. Although not the focus of this course, there is a very rich application domain, including computer graphics, computer-aided design and manufacturing, machine learning, robotics, geographic information systems, computer vision, integrated circuit design, and many other fields.

The course introduces the most important tools used in the design of computational geomtric algorithms. The larger part of the course will deal with problems that can be solved exacly in near-linear time, which are practically solvable even on very large inputs. Towards the end we will deal with hard (often NP-hard) problems, and see some tools that help in creating approximation algorithms.