Optimization Problems in Computational Topology

A project involving members of the University of Illinois at Urbana-Champaign (UIUC) and French researchers, funded by CNRS, INRIA, and UIUC for two years (2005-2006).

Summary of Objectives

Computational topology is a rapidly emerging area that aims at studying efficient algorithms for topological problems. We propose to work together on optimization problems in computational topology of curves on surfaces. Previous works focused on computing topological objects (such as topological decompositions of surfaces with curves) or on deciding topological properties (such as testing whether there exists a continuous transformation between two curves). Here, we want to compute the shortest family of curves (with respect to a given length function) among all families of curves sharing some topological properties. These questions arise naturally from a theoretical viewpoint and we believe them to be also relevant in several applied domains, notably computer graphics.

Keywords: algorithms, computational topology, optimization, surface decomposition.


  • Walking your dog in the woods in polynomial time;
  • Splitting (complicated) surfaces is hard;
  • Tightening non-simple curves on surfaces.
  • Members

  • UIUC:
  • Jeff Erickson (UIUC), coordinator,
  • Sariel Har-Peled (UIUC).
  • France:
  • Éric Colin de Verdière (ENS, Paris), coordinator,
  • Sylvain Lazard (LORIA, Nancy),
  • Francis Lazarus (LIS, Grenoble),
  • Monique Teillaud (INRIA, Sophia-Antipolis).
  • Other interested people (non-exhaustive list...):
  • Julien Demouth (LORIA, Nancy),
  • Hazel Everett (LORIA, Nancy),
  • Marc Glisse (LORIA, Nancy),
  • Xavier Goaoc (LORIA, Nancy),
  • Luc Habert (ENS, Paris),
  • Sylvain Petitjean (LORIA, Nancy),
  • Vincent Pilaud (ENS, Paris),
  • Michel Pocchiola (ENS, Paris),
  • Shripad Thite (U. Eindhoven, The Netherlands, formerly UIUC),
  • Kim Whittlesey (UIUC),
  • Erin Wolf Chambers (UIUC).
  • Travel plans

  • 2005.10.26 - 2005.11.09: Francis and Éric visit UIUC;
  • 2005.11.21 - 2005.11.25: general meeting at ENS Paris;
  • 2006.05.16 - 2006.05.20: general meeting at INRIA Nancy;
  • 2006.09.10 - 2006.09.22: Francis and Éric visit UIUC.
  • Administrative details

    Administrative setting: see here and here for the details.