Xavier Goaoc : « Faire se rejoindre mathématique et informatique en géométrie »

Vous travaillez sur la géométrie algorithmique. Pouvez-vous nous dire ce que cela recouvre ?

Xavier Goaoc : De nombreux problèmes de la vie courante peuvent se formuler en termes géométriques : recherche de chemins, éclairage d’une pièce, rangement optimal d’une famille d’objets dans un espace restreint. Il est souvent souhaitable de résoudre, ou simuler, ces questions informatiquement, par exemple pour proposer un itinéraire, réaliser des images de synthèse ou automatiser la gestion d’un entrepôt. La géométrie algorithmique étudie les fondements algorithmiques de ce traitement par ordinateur de questions géométriques. 
L’efficacité d’une solution informatique à un problème géométrique repose sur une bonne articulation entre les algorithmes et les objets mathématiques qui décrivent le problème. Ces objets mathématiques sont parfois élémentaires (points, droites, triangles…) mais il leur arrive aussi d’être compliqués (familles de droites, courbes algébriques, espaces topologiques…). La géométrie algorithmique travaille donc non seulement à améliorer les algorithmes, mais aussi à mieux comprendre les propriétés de ces objets mathématiques. C’est plutôt sur ce second type de questions que je travaille.

Comment en êtes-vous venu à étudier ces questions ?

X. G. : Lors de ma thèse, je me suis intéressé à des aspects géométriques de la simulation d’éclairage en synthèse d’image, par exemple le calcul de contours d’ombres. Comme la lumière se propage en ligne droite, ces contours d’ombres sont tracés par des ensembles de droites définis implicitement par les objets de la scène que l’on essaie d’éclairer. Pour un informaticien, ne pas pleinement comprendre ces objets mathématiques que sont les ensembles de droites est bloquant, aussi m’y suis-je intéressé. Ces questions de géométrie des droites sont communes à d’autres problèmes ; je les ai, par exemple, croisées quelques années plus tard en travaillant sur des questions de vision par ordinateur. Avec un appareil photo standard, prendre une photo revient à projeter une scène en 3D (le monde) sur un plan 2D (la photo) en passant par un seul point (l’objectif). Le procédé inverse est possible, et l’on peut extraire d’un ensemble de photos des informations de profondeur pour construire un modèle tri-dimensionnel de la scène ; c’est la stéréoreconstruction. Nous souhaitions cette fois étendre cette méthode de stéréoreconstruction à des appareils photo "non-centraux". Là encore, les structures mathématiques sous-jacentes sont des variétés de droites et leur compréhension est la clef qui permet d’étendre les algorithmes existants.

X. G. : Je travaille à comprendre des structures dites "de recouvrement", c’est-à-dire la manière dont un ensemble de formes élémentaires peuvent interagir et en particulier se chevaucher. Ces questions apparaissent dans des domaines très divers (maillage, algorithmes d’optimisation, réseau…) sous des aspects variés, mais là encore l’objet mathématique sous-jacent est le même. Pour étudier ces questions, je puise principalement dans deux types d’outils mathématiques, la topologie algébrique et la géométrie probabiliste. La topologie est l’étude des propriétés géométrique qui restent inchangées par transformations continues : il est ainsi possible de déformer, étirer, mais pas de découper. 
La topologie algébrique étudie cette "géométrie élastique" par des méthodes d’algèbre. Les structures de recouvrement apparaissent naturellement dans ce domaine, et les chercheurs de cette communauté se sont posé des questions proches de celles qui intéressent les informaticiens. La géométrie probabiliste s’intéresse à des objets géométriques aléatoires, et les outils qu’elle développe permettent notamment d’améliorer des algorithmes géométriques en en comprenant mieux le comportement moyen. Dans les deux cas la démarche est la même : travailler avec des collègues de ces disciplines (dans le cadre d’un ANR Blanc, Présage, pour la géométrie probabiliste) afin d’apprendre leur langage et de faire percoler leurs avancées vers ma discipline, en les adaptant aux nouvelles questions que pose l’informatique.