Séminaire

Le nombre geometrique d’intersections d’une courbe C est le nombre minimum d’auto-intersections parmi toutes les courbes qui peuvent être obtenues par homotopie (déformations continues) à partir de celle ci. Le problème a été largement étudié dans la communauté mathématique et plusieurs de ces travaux sont de nature algorithmique. Malheureusement, leur utilisation n’est pas toujours possible directement et, pour la plupart, ils ne s’appliquent que dans un cadre particulier. Nous décrivons des algorithmes simples et généraux qui nous permettent de résoudre le problème en temps O(n+l^2) où l est la longueur de C et n est la complexité de S.