A tour of algorithms for curves on surfaces

1 : CNRS

CNRS : UMR5216

2 : Optimisation Combinatoire

Laboratoire des sciences pour la conception, l\'optimisation et la production

In this talk I will consider closed curves drawn on a surface and look at topological or geometric questions such as: Can this curve be deformed continuously to this other curve? What if we additionally require that the length of the curves do not exceed some fixed length during the deformation? Among all continuous deformations of a curve, what is the minimal number of self-intersections, or how long is the shortest curve?

I will survey recent techniques to answer these questions efficiently in a discrete setting where the curves and the surface are described in a combinatorial way, say by closed walks on a triangulation.