L'organisation structurée (graphe avec hiérarchies et propriétés sémantiques) d'objets du plan implique plusieurs opérations complexes qui doivent être effectuées en toute sécurité de cohérence topologique. La précision inhérente d'une machine étant nécessairement limitée, il faut souvent recourir à une arithmétique exacte couteuse. Cette thèse présente, à partir de travaux liés à la réalisation du module de facettisation d'un simulateur de vol industriel, une solution permettant l'utilisation d'une arithmétique mixte, de précision arbitraire et de coût très inférieur statistiquement a la solution exacte. On y trouve aussi l'unification des méthodes de construction d'un diagramme de Voronoi, d'une triangulation de Delaunay pour un nuage de points dans le plan et de la triangulation contrainte de Delaunay de la représentation par segments d'un graphe planaire, autour d'une technique incrémentale optimale, fondamentalement plus simple que la méthode diviser-pour-résoudre classique. La technique incrémentale permet, par ailleurs, de donner un algorithme linéaire et très simple de construction du diagramme de Voronoi et de la triangulation de Delaunay d'un nuage de points situes sur la frontière d'un polygone monotone ou convexe.

Dans cette thèse, nous proposons une méthode de résolution des problèmes de la géométrie algorithmique posés pour des objets courbes (par opposition aux objets "linéaires" : ensembles de points, segments, polygones ...). Les objets que nous étudions sont des courbes de Bézier composites, choisies, d'une part, pour le réalisme qu'elles assurent dans la modélisation géométrique, et d'autre part, pour la facilité du traitement algorithmique que leurs propriétés offrent. Notre approche met l'accent sur les aspects topologiques des problèmes abordés, en évitant les incohérences que la résolution en arithmétique flottante d'équations algébriques de degré élevé (générées par le traitement direct des courbes) peut le plus souvent introduire. Cet objectif est atteint par l'utilisation d'approximations polygonales convergentes, qui dans le cas des courbes de Bézier sont naturellement fournies par les polygones de controle par l'intermédiaire de la subdivision de de Casteljau. Deux des problèmes fondamentaux de la géométrie algorithmique sont traités ici, l'enveloppe convexe et les arrangements, les deux en dimension 2. Dans le cas des arrangements, la notion de topologie (combinatoire) est bien connue ; dans celui de l'enveloppe convexe, nous la définissons rigoureusement. Pour les deux problèmes, nous montrons qu'il est possible d'obtenir toute l'information topologique définissant (de manière, il est vrai, implicite, mais correcte et complète) la solution exacte en travaillant exclusivement sur les approximations polygonales des objets donnés. Les résultats théoriques obtenus sont concrétisés par des algorithmes dont la convergence et la correction sont démontrées et pour lesquels des études de cout sont réalisées. Des exemples illustrent le fonctionnement de ces algorithmes, validant la méthode proposée.

Les progrès enregistrés en modélisation solide ont beaucoup contribué à l'essor des diverses applications de la CAO/FAO, de la robotique et de la synthèse d'images. Les systèmes de modélisation solide contemporains combinent souvent la représentation par arbre de construction et la représentation par frontière afin de mieux répondre aux besoins des applications. Dans cette thèse nous proposons une nouvelle méthode de calcul de la frontière d'un objet polyédrique décrit par un arbre de construction, qui traite uniformément les nombreux cas particuliers et qui résout le problème crucial des imprécisions numériques inhérentes à l'arithmétique flottante. Une implantation utilisant une arithmétique rationnelle optimisée est présentée ainsi que des résultats de tests.