Geometric algorithms with limited resources

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: https://lists.mpi-inf.mpg.de/listinfo/geoalgolr