Best Paper Award à la SoCG
12 novembre 2020
Xavier Goaoc, professeur à l’université de Lorraine et chercheur dans l’équipe commune
Gamble (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.
L’article met en lumière un résultat des mathématiques discrètes (1), et plus précisément de géométrie combinatoire ayant des conséquences en géométrie algorithmique (2). 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.
(1) Soit l’étude des structures mathématiques fondamentalement discrètes, par opposition aux structures continues .
(2) Domaine de l’algorithmique qui traite des algorithmes manipulant des concepts géométriques.
Source des définitions : Wikipédia