Översikt

  • Computational Geometry 2023 Spring

    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:
    The grades will be determined by weekly assignments submitted in pdf via A+ here:
    https://plus.cs.aalto.fi/cs-e4720/2023spring/
    Students are expected to attend the lectures and the tutorials.

    Lectures:
    Sándor Kisfaludi-Bak (sandor.kisfaludi-bak at aalto.fi)
    Lectures: Wednesdays 14:00-15:30, in A133 (T5) from January 11 to April 5 (except Feb 22.)
    First Lecture: January 11, 14:00-15:30, in A133 (T5) 

    Teaching Assistant:

    Geert van Wordragen (geert.vanwordragen at aalto.fi)
    Tutorials: Fridays 10:15-12:00, in A136 (T6) from January 13 (to be confirmed) to April 14 (except Feb 24 and April 7)



    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