Directory Intranet
You are here : GIPSA-lab
Chargement
Distinction

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

2017-08-21

Francis LAZARUS, équipe AGPiG et Vincent DESPRE, ENS-Lyon ont obtenu le Best paper award du 33rd International Symposium on Computational Geometry qui s'est tenu à Brisbane (Australie) du 4 au 7 juillet 2017. Principale conférence en géométrie algorithmique, SoCG a récompensé les 2 chercheurs pour leur article intitulé "Computing the Geometric Intersection Number of Curves".

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


GIPSA-lab, 11 rue des Mathématiques, Grenoble Campus BP46, F-38402 SAINT MARTIN D'HERES CEDEX - 33 (0)4 76 82 71 31