Best Paper Award à la SoCG pour Xavier Goaoc

Xavier Goaoc, professeur à l’université de Lorraine et chercheur dans l’équipe commune Gamble du Loria (CNRS, Inria et Université de Lorraine) a obtenu un Best Paper Award lors de la 36ème édition de la SoCG. Cet événement fait partie de la Computational Geometry Week, un prestigieux forum international spécialisé dans le domaine de la géométrie algorithmique et ses nombreuses applications.

Convex Hulls of Random Order Types a été co-rédigé avec Emo Welzl, chercheur en géométrie algorithmique et professeur au Département d’informatique de l’École polytechnique fédérale de Zurich en Suisse.

L’article met en lumière un résultat des mathématiques discrètes1, et plus précisément de géométrie combinatoire ayant des conséquences en géométrie algorithmique2. Xavier Goaoc et Emo Welzl ont trouvé une nouvelle façon d’étudier les objets géométriques que sont les types d’ordre. Cette technique leur a permis de révéler que prendre des points au hasard dans une forme géométrique, technique naturelle de “pêche aux bugs” en géométrie algorithmique et de “pêche aux contre-exemples” en géométrie combinatoire, produit des types d’ordres singulièrement peu variés. Cette approche est donc peu efficace lorsque le problème sous-jacent ne dépend que du type d’ordre (comme c’est le cas pour certains algorithmes de calcul d’enveloppe convexe ou dans la conjecture d’Erdös-Szekeres, Happy ending problem).

Quelques précisions…

Il existe des algorithmes dont la donnée d’entrée est un nuage de points (par exemple le calcul d’enveloppe convexe, cité ci-dessus) et des conjectures qui portent sur des nuages de points (par exemple la conjecture du Happy ending problem).

Il est tentant d’aller “à la pêche” aux bugs (pour les algorithmes) et aux contre-exemples (pour les conjectures) en considérant des ensembles de points pris au hasard.

Certains algorithmes ou conjecture dépendent uniquement du “type d’ordre” de l’ensemble de points considéré (c’est le cas de certains algorithmes de calcul d’enveloppe convexe, ainsi que de la conjecture du Happy ending problem, cf. lien ci-dessus). Dans ces cas, on sait d’avance que deux ensembles de points de mêmes types d’ordres donneront les mêmes réponses, et que tester les deux c’est faire du travail redondant.

Le résultat de Xavier Goaoc et Emo Welzl implique que les méthodes usuelles de génération de points aléatoires produisent des ensembles qui ont des types d’ordre singulièrement peu diversifiés. Cela implique donc que ces méthodes usuelles sont mauvaises pour tester algorithmes ou conjectures qui ne dépendent que des types d’ordre.

Ce résultat s’inscrit dans une recherche fondamentale visant à mieux comprendre les types d’ordre.