Géométrica a pour but de développer une approche axiomatique du calcul géométrique : conception d'algorithmes basée sur des primitives simples vérifiant un ensemble fini d'axiomes.
La particularité du calcul géométrique tient au fait que les objets géométriques sont à la fois combinatoires et numériques. Par exemple, un polyèdre, une triangulation ou une carte planaire sont représentés par un graphe décrivant leur structure faciale et des valeurs numériques donnant les équations des faces. Non seulement la structure combinatoire de l'objet calculé dépend d'une série de tests numériques mais une certaine cohérence entre cette structure et les valeurs numériques qui l'accompagnent est en général requise, voire cruciale pour la fiabilité de l'algorithme. Traitements numériques et décisions logiques sont donc intimement mêlés dans le calcul géométrique et sont la source de problèmes de robustesse bien connus mais difficiles à surmonter.
L'approche axiomatique n'est évidemment pas nouvelle. Elle a brillamment été défendue par D. Knuth [3] dans une monographie intitulée ``Axioms and Hulls'' où l'auteur présente une analyse axiomatique des ensembles de points en dimension 2 qui s'applique naturellement aux problèmes de l'enveloppe convexe et de la triangulation de Delaunay. Elle apparait en filigrane dans les développements les plus spectaculaires de la géométrie algorithmique de ces 10 dernières années dus essentiellement à une bonne modélisation ou abstraction combinatoire des données géométriques : les cadres combinatoires développés autour de la méthode probabiliste en géométrie (dimension de Vapnik-Chervonenkis d'un hypergraphe), la programmation linéaire (programmation linéaire généralisée) ou encore la théorie des arrangements (matroides orientés) attestent de ce mouvement.
Une tendance récente pour résoudre les problèmes de robustesse consiste à analyser les algorithmes géométriques en distinguant les prédicats (test numériques qui conditionnent les branchements effectués par l'algorithnme) et les constructeurs (calcul du plongement géométrique de la structure combinatoire résultante). L'approche axiomatique doit permettre d'analyser l'ensemble des prédicats évalués par un algorithme. Il s'agit par exemple de dégager un ensemble minimal de prédicats, de mesurer l'influence des prédicats sur la complexité des algorithmes, ou encore de développer un test certifiant la cohérence des résultats de ces prédicats, ce qui conduit naturellement à une programmation fiable (voire certifiée) des algorithmes géométriques.
Outre l'apport conceptuel, l'approche axiomatique devient indispensable au développement de logiciels de calcul géométrique. L'effort de recherche envisagé trouvera une application directe dans le développement de la bibliothèque de programmes géométriques CGAL.
Dans un premier temps, l'action incitative GÉOMÉTRICA envisage d'étudier plus particulièrement l'algorithmique des graphes de visibilité, des arrangements de courbes et de surfaces. Ces questions sont à la base d'un très grand nombre d'applications : calcul de vues, recherche de plus courts chemins, opérations ensemblistes sur les objets géométriques, etc.
D'un point de vue théorique il s'agit d'axiomatiser la classe des arrangements de courbes qui représentent dans l'espace dual l'ensemble des tangentes à une collection de convexes du plan [4,5]. Cette classe contient la classe des arrangements de droites et ``s'apparente'' à une sous-classe de la classe des arrangements de pseudodroites. Cette dernière est axiomatisée par la notion de matroide orienté de rang 3. L'un des outils de cette axiomatisation devrait être la recherche d'invariants par l'opération de mutation, opération empruntée à la théorie des matroides orientés et proprement généralisée au cadre des collections de convexes. Un certain nombre de retombées sur l'algorithmique des graphes de visibilité et des arrangements de droites ont déjà été obtenus dans cette direction de recherche suite, entre autres, au stage de DEA de P. Angelier. Il s'agit donc d'affiner ces résultats et d'en élaborer de nouveaux.
Plusieurs résultats ont déjà été obtenus concernant les prédicats géométriques requis pour construire un arrangement de segments [1,2]. Cependant l'axiomatisation des arrangements de segments courbes en est encore à un stade embryonnaire. Il s'agit de poursuivre cette étude et de la généraliser en dimension 3 aux arrangements de carreaux de surfaces.
D'un point de vue logiciel, ces travaux conduiront au développement de code pour construire er des pseudotriangulations, des couvertures polygonales, pour le calcul partiel d'arrangements de courbes ou de surfaces ainsi qu'à diverses applications : graphe de visibilité, plus courts chemins, superposition d'arrangements.