Computational Geometry

About the course

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. You will learn to apply various algorithmic approaches, and assess their strong and weak points in a particular context, thus gaining an ability to choose the most appropriate method for a particular problem.

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.