Topic outline

  • Computational Geometry 2024 Spring

    We now have a Zulip chat here: https://cg-2024.zulip.aalto.fi/.


    Description:

    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 a point set, finding clusters, or setting up a data structure to find the nearest point to a given query point. Although not the main 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.

    Grading:
    Grades will be primarily based on the exam at the end of the course, but a significant amount of points can be gained via solving/presenting homework problems for the tutorials. You can also get further bonus points if you participate in a challenge or volunteer to be a scribe.

    Lectures:
    Sándor Kisfaludi-Bak (sandor.kisfaludi-bak at aalto.fi)
    Lectures: Mondays 14:15-16:00, in A133 (T5) from January 8 to April 8 (except February 19 and April 1.)
    First Lecture: January 8, 14:00-16:00, in A133 (T5) 

    Teaching Assistant:

    Geert van Wordragen (geert.vanwordragen at aalto.fi)
    Tutorials: Fridays 10:15-12:00, in A136 (T6) from January 12 to April 12 (except February 23 and March 29)



    Learning outcomes:

    You know the most important data structures and algorithms used in geometric processing. You can design and analyze basic geometric algorithms. You have some understanding of computational hardness for geometric problems, and are familiar with several tools used in geometric approximation algorithms. 


    Prerequisites:

    Basic knowledge of algorithms, computational complexity, linear algebra, and discrete probability.


    Literature:

    • Computational Geometry: Algorithms and Applications (3rd ed) by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.
    • Geometric Approximation Algorithms by Sariel Har-Peled
    • Lectures on Discrete Geometry by Jiří Matoušek