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.