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.
Results
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.