Nicolas Brisebarre

From the 11th to the 15th of January 2010 — ENS Lyon

Goals

More and more fields like biology, statistical analysis or machine learning, have to deal with data which are actually scatter plots in high dimensional spaces. These data have some topological and geometrical characteristics that express the properties of the modelled systems. For instance, the density of a scatter plot may be concentrated around a variety of intrinsic dimension much lesser that the one of the ambient space. Extracting such an information is not an easy task. First, the data suffer from some noise. Then, the structures and the algorithms of algorithmic geometry often have complexities that increase exponentially with the dimension and are not well scalable for this kind of data.

This series of lectures proposes an introduction to algorithmic geometry, focused on the approximation and geometrical object sampling issues. It starts from classical concepts (convex hull, Voronoi diagrams) and addresses recently developed methods (core sets, topological persistence) in order to approximate the geometrical and topological properties of higher dimension objects, while avoiding the exponential explosion of complexity related to the dimension.

Lecturers

  1. Jean-Daniel Boissonnat
  2. Frédéric Chazal
  3. Mariette Yvinec

Outline of the course

Algorithms for geometric approximation

  1. Metric structures for point sets
    • Convex hulls, Voronoi diagrams and Delaunay triangulations (J.-D. Boissonnat)
    • Dimension reduction, approximate nearest neighbor search, the k-means algorithm (F. Chazal)
    • Randomized algorithms and core sets (M. Yvinec)
  2. Simplicial approximation of manifolds
    • Mesh generation by Delaunay refinement (M. Yvinec)
    • Restricted Delaunay triangulation, e-samples and surface mesh generation (J.-D. Boissonnat)
    • Manifold reconstruction in 3 and higher dimensions (J.-D. Boissonnat)
  3. Geometric inference (F. Chazal)
    • Sampling theory for compact sets
    • Persistent homology and data analysis

Prerequisite

The course is self-contained.

Bibliography

  • M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
  • J.-D. Boissonnat and M. Teillaud, editors. Effective Computational Geometry for Curves and Surfaces, Springer-Verlag, 2006.
  • J.-D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by Hervé Brönnimann.
  • F. Chazal, D. Cohen-Steiner, Geometric Inference, submitted as a chapter in a book entitled “Tesselations in the Sciences”, November 2007.
  • F. Chazal, D. Cohen-Steiner, A. Lieutier, A Sampling Theory for Compacts in Euclidean Space, Proceedings of the 22nd ACM Symposium on Computational Geometry 2006.
  • E. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge, 2001.
  • K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
  • A. Zomorodian, Topology for Computing, Cambridge Monographs on Applied and Computational Mathematics, cambridge University Press, 2005.

Registration

There are no registration fees. For organization reasons it is however necessary to register online; [registration closed].

Location and schedule

All the lectures will take place in “amphithéatre B”, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon).
A tentative schedule:

  • Monday, January 11
    • 2:00 PM – 5:00 PM. Convex hulls, Voronoi diagrams and Delaunay triangulations (J.-D. Boissonnat).
      Slides available here then here.
  • Tuesday, January 12
    • 8:30 AM – 11:30 AM. Mesh generation by Delaunay refinement (M. Yvinec).
      Slides available here then here.
    • 1:30 PM – 4:30 PM. Restricted Delaunay triangulation, e-samples and surface mesh generation (J.-D. Boissonnat).
      Slides available here.
  • Wednesday, January 13
    • 8:30 AM – 11:30 AM. Dimension reduction, approximate nearest neighbor search, the k-means algorithm (F. Chazal).
      Slides available here.
    • 1:30 PM – 4:30 PM. Randomized algorithms and core sets (M. Yvinec).
      Slides available here then here.
  • Thursday, January 14
    • 8:30 AM – 11:30 AM. Sampling theory for compact sets (F. Chazal).
      Slides available here.
  • Friday, January 15
    • 8:30 AM – 11:30 AM. Manifold reconstruction in 3 and higher dimensions (J.-D. Boissonnat).
      Slides available here.
    • 1:00 PM – 4:00 PM. Persistent homology and data analysis (F. Chazal).
      Slides available here.

Local organizers

There are several useful informations on the main page of the research schools in Computer Science at ENS Lyon.