Best Paper Award de la conférence SoCG - Brisbane, 4-7 Juillet 2017

Référence : Vincent Despré, Francis Lazarus. Computing the Geometric Intersection Number of Curves, June 24, 2016

Résumé :
Il n'est pas difficile de se persuader que toute courbe fermée tracée sur une feuille de papier peut être déformée continuement en un cercle quand bien même la courbe se croiserait plusieurs fois. Une telle déformation élimine les éventuels croisements de la courbe puisque le cercle est une courbe simple, c'est-à-dire une courbe sans croisement.
Si l'on remplace la feuille de papier pas une autre surface, telle que la surface d'une bouée, les choses se compliquent. Certaines courbes peuvent être déformée en une courbe simple et d'autres pas. Dans le cinquième et dernier complément de son célèbre Analysis Situs, Poincaré propose une méthode pour reconnaître les courbes qui se déforment en des courbes simples. Au cours du 20e siècle de nombreux mathématicien(e)s ont proposé des algorithmes fondés sur la méthode de Poincaré mais ces algorithmes sont complexes et peu efficaces en pratique. Dans ce travail, les chercheurs proposent un algorithme particulièrement simple et de faible complexité pour le problème de Poincaré : un algorithme pour calculer le nombre géométrique d'intersection d'une courbe tracée sur une surface, c'est-à-dire le nombre minimal de croisements de toute courbe pouvant être obtenue par déformation continue sur la surface.

>> SoCG Website