Geometric algorithms with limited resources

Advanced Course, 2+1

Basic Information

Lectures:Tuesday 10:00-12:00 Location: Zoom,
Lecturers:Themistoklis Gouleakis and Sándor Kisfaludi-Bak
First lecture:13.04.2021, 10:00 am
Tutorials:Friday 10:00
Teaching Assistant:Hannaneh Akrami
First tutorial:16.04.2021, 10:00 am
Prerequisites:Basics of data structures, algorithms, linear algebra, probability


All students should subscribe to the following mailing list:

The course will be held in the following Zoom room:

If you still need the password for the Zoom room, please send one of the lecturers an email.


Spatial data arises in several settings: it may come directly from geometic data (such as GPS coordinates, pixels and their locations in a digital picture, or voxels in a brain scan), but it is also often useful to regard any data as a point set in high-dimensional space. The goal of the course is to look at algorithms that are able to process such data even with very limited resources, e.g. using very limited (sublinear) computation time or space. We will look at several types of resource restrictions, such as property testing, sublinear algorithms, constant workspace algorithms, and the usual algorithmic design techniques used in these settings. These allow one to make useful inferences from spatial data even with very limited resources.



Join the course mailing list here:



13.04Introduction, concepts from computational geometrySándor Kisfaludi-Bakpdf
20.04Introdcution to sublinear algroithmsThemistoklis Gouleakis 
27.04Property testing in Eudlidean spaceSándor Kisfaludi-Bak 
04.05Sublinear algorithms in metric spacesThemistoklis Gouleakis