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.

Enroll in a course:
Course's authors:

  • Alexander Kulikov
    Senior research fellow at Steklov Institute of Mathematics at St. Petersburg, Russian Academy of Sciences, founder and board member of Computer Science Center

  • Aliaksei Tolstsikov
    Senior lecturer

  • Kira Vyatkina
    Leading Researcher
©Санкт-Петербургский государственный университет
2021 год