Computational Geometry

This course represents an introduction to computational geometry — a branch of algorithm theory that aims at solving problems about geometric objects. Its application areas include computer graphics, computer-aided design and geographic information systems, robotics, and many others. We will cover a number of core computational geometry tasks, such as: - testing point inclusion in a polygon, - computing the convex hull of a point set, - intersecting line segments, - triangulating a polygon, - and processing orthogonal range queries. Special attention will be paid to a proper representation of geometric primitives and evaluation of geometric predicates, which are crucial for an efficient implementation of an algorithm. Each module includes a selection of programming tasks that will help you both to strengthen the newly acquired knowledge and improve your competitive coding skills.

The programme consists of 5 moduls: 1. Point inclusion in a polygon 2. Convex hulls 3. Intersections 4. Polygon triangulation 5. Orthogonal range search