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 Gouleakispdf
27.04Low-dimensional linear programming in sublinear spaceSándor Kisfaludi-Bakpdf
04.05Testing convexityThemistoklis Gouleakis    pdf
11.05Deciding intersection of convex objectsSándor Kisfaludi-Bakpdf
18.05Sparse image testingThemistoklis Gouleakispdf
25.05Deciding intersection of convex objects 2Sándor Kisfaludi-Bakpdf
01.06Sparse image testing 2Themistoklis Gouleakispdf
08.06Ray shooting and volume approximationSándor Kisfaludi-Bakpdf
22.06Learning Halfspaces-Perceptron algorithmThemistoklis Gouleakispdf
29.06Volume approximation 2Sándor Kisfaludi-Bakpdf
06.07TBAThemistoklis Gouleakispdf


The recordings are available here, and the annotated slides are here.