Schnelleinstieg Reader


Startseite FSU

Approximate Methods in Geometry

This is class is about approximate geometric methods for high dimensional point cloud data. We will discuss (optimization) problems that arise frequently in machine learning like:

  • Given a finite set of points in Euclidean and a query point. Compute the k nearest neighbors of the query in the point set.
  • Given a finite set of points in Euclidean space. Compute the smallest ball containing all the points.
  • Given two finite point sets in Euclidean space. Compute the distance of the convex hull of the two point sets.
  • Given a finite metric space. Compute an embedding of the points of this space into a low dimensional Euclidean space such that distances are approximately preserved.
  • Given a finite set X of points in Euclidean space and a set of subsets of X. Compute a subset of X that hits every sufficiently large set in the subset system.

All these problems are costly to solve exactly once the dimension of the Euclidean space is large. Thus one often has to resort to approximate methods. We will learn about random sampling, core sets, well separated pair decompositions, and space space partitions to solve the above mentioned problems approximately. 

Suggested reading:

  • Jiri Matousek. Lectures on Discrete Geometry. Springer Verlag
  • Sariel Har Peled. Approximation algorithms in Geometry (lecture notes)

Please register for this class through CAJ (only for registered users).

Material for the Practical Part

Wordcloud Git Repository