De la géométrie algorithmique au calcul géométrique

In this thesis, we define efficient and generic methods in order to solve the robustness problems that arise in the field of computational geometry, and we concentrate especially on the exact evaluation of the geometric predicates. We investigated methods based on modular arithmetic, which led us to develop simple and efficient algorithms to reconstruct the sign in this number representation. We also developed new kinds of arithmetic filters, which allow to speed up the exact computation of predicates, working around the cost of traditionnal solutions based on generic multiprecision computations. Our methods are based on the use of interval arithmetic, which allows an efficient and simple use, combined to an automatic generation tool of the predicates code. These solutions are now available in the CGAL library of geometric algorithms.Dans cette thèse, nous définissons des méthodes efficaces et génériques dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique, en se concentrant principalement sur l'évaluation exacte des prédicats géométriques. Nous avons exploré des méthodes basées sur l'arithmétique modulaire, ce qui nous a conduits à mettre au point des algorithmes simples et efficaces de reconstruction du signe dans cette représentation des nombres. Nous avons également mis au point de nouveaux types de filtres arithmétiques qui permettent d'accélérer le calcul des prédicats exacts, en contournant le coût des solutions traditionnelles basées sur des calculs multi-précision génériques. Nos méthodes sont basées sur l'utilisation de l'arithmétique d'intervalles, qui permet une utilisation souple et efficace, combinée à un outil de génération automatique de code des prédicats. Ces solutions sont maintenant disponibles dans la bibliothèque d'algorithmes géométriques CGAL