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 is taught online and includes recorded lectures and tests.
 

The programme consists of 5 moduls:

1. Point inclusion in a polygon

2. Convex hulls

3. Intersections

4. Polygon triangulation

5. Orthogonal range search

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.