Calculer vite est important mais calculer de manière fiable l’est peut-être encore plus. Cette question est moins simple qu’il n’y paraît. Les pionniers de la géométrie algorithmique ont analysé les performances des algorithmes en faisant l’hypothèse que toutes les opérations sur les nombres réels pouvaient être effectuées de façon exacte pour un coût unitaire. Un tel modèle de calcul permet de se concentrer sur l’estimation asymptotique de la complexité des algorithmes mais ignore complètement le fait que les ordinateurs travaillent avec des représentations finies des nombres.
Ceci est particulièrement problématique en géométrie algorithmique où l’on cherche à construire des structures combinatoires (comme l’enveloppe convexe d’un ensemble fini de points) en se reposant sur des opérations numériques liées au plongement de ces structures. Cette dimension arithmétique du calcul géométrique a longtemps constitué un frein à la diffusion des techniques de la géométrie algorithmique.
Ce cours distingue les prédicats des constructions géométriques et analyse précisément les besoins en précision numérique de quelques algorithmes géométriques fondamentaux. Une question-clé est l’évaluation exacte du signe de polynômes dont les variables sont les données d’entrée. Tous les algorithmes résolvant le même problème n’ont pas nécessairement la même complexité algébrique comme le montre l’exemple du calcul de l’arrangement de segments du plan. Un autre exemple est donné par le complexe à témoins qui n’utilise que des polynômes de degré 2 mais permet d’approcher, sous certaines conditions, une triangulation de Delaunay dont le degré est d + 2 et dépend de la dimension de l’espace de travail. Les développements théorique et pratique du calcul géométrique ont conduit à des avancées spectaculaires dont la bibliothèque logicielle CGAL est un exemple. On peut aujourd’hui certifier les résultats fournis par la plupart des algorithmes géométriques fondamentaux sans en dégrader significativement les performances.
