La majorité des courbes et surfaces rencontrées dans la modélisation géométrique sont définies comme l'ensemble des solutions d'un système d'équations et d'inéquations algébriques (ensemble semi-algébrique). De nombreux problèmes dans différentes disciplines scientifiques font appel à des requètes de proximité telles que la recherche du ou des voisins les plus proches ou la quantification du voisinage de deux objets.<br /><br />Le diagramme de Voronoï d'un ensemble d'objets est une décomposition de l'espace en zones de proximité. La zone de proximité d'un objet est l'ensemble des points plus proches de cet objet que de tout autre objet. Les diagrammes de Voronoï permettent de répondre aux requètes de proximité après avoir identifié la zone de proximité à laquelle le point objet de la requète appartient. Le graphe dual du diagramme de Voronoï est appelé le graphe de Delaunay. Seules les approximations par des coniques peuvent garantir un ordre de continuité approprié au niveau des points de contact, ce qui est nécessaire pour garantir l'exactitude du graphe de Delaunay.<br /><br />L'objectif théorique de cette thèse est la mise en évidence des propriétés algébriques et géométriques élémentaires de la courbe déplacée d'une courbe algébrique et de réduire le calcul semi-algébrique du graphe de Delaunay à des calculs de valeurs propres. L'objectif pratique de cette thèse est le calcul certifié du graphe de Delaunay pour des ensembles semi-algébriques de faible degré dans le plan euclidien.<br /><br />La méthodologie associe l'analyse par intervalles et la géométrie algébrique algorithmique. L'idée centrale de cette thèse est qu'un pré-traitement symbolique unique peut accélérer l'évaluation numérique certifiée du détecteur de conflits dans le graphe de Delaunay. Le pré-traitement symbolique est le calcul de l'équation implicite de la courbe déplacée généralisée d'une conique. La réduction du problème semi-algébrique de la détection de conflits dans le graphe de Delaunay à un problème d'algèbre linéaire a été possible grâce à la considération du sommet de Voronoï généralisé (un concept introduit dans cette thèse).<br /><br />Le calcul numérique certifié du graphe de Delaunay a été éffectué avec une librairie de résolution de systèmes zéro-dimensionnels d'équations et d'inéquations algébriques basée sur l'analyse d'intervalles (ALIAS). Le calcul certifié du graphe de Delaunay repose sur des théorèmes sur l'unicité de racines dans des intervalles donnés (Kantorovitch et Moore-Krawczyk). Pour les coniques, les calculs sont accélérés lorsque l'on ne considère que les équations implicites des courbes déplacées.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00005932 |
| Date | 11 December 2003 |
| Creators | Anton, François |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0039 seconds