Triangulation de Delaunay et arbres multidimensionnels - Mines Saint-Étienne Accéder directement au contenu
Thèse Année : 1997

Triangulation de Delaunay et arbres multidimensionnels

Résumé

This thesis deals mainly with Delaunay triangulations. It is shown that the average complexity of k-dimensional merge processes - according to unRnished sites - is linear, assuming the sites to be quasy-uniformly distributed in an hypercube. This general result is applied to the two-dimensional case, and allows to analyze new Delaunay triangulation algorithms which perform better than those known to this day. The underlying principle is to divide the domain according to k-dimensional trees (quadtree, 2d-tree, bucket-tree. . . ), and then to merge the obtained cells along two directions. We are currently trying to generalize these algorithms to the constrained case (graphs with constraints, and not only vertices). We propose new point location algorithmsC based upon randomisation on a dynamic binary search tree AVL. One of them is faster than Kirkpatrick's optimal algorithm at least up to 12 millions of sites. Their formal average analysis is being done. We use this algorithm to build Delaunay triangulations "on-line" which is one of the most performant known "on-line" method.
Les travaux effectués lors de cette thèse concernent principalement la triangulation de Delaunay. On montre que la complexité en moyenne - en termes de sites inachevés - du processus de fusion multidimensionnelle dans l'hypothèse de distribution quasi-uniforme dans un hypercube est linéaire en moyenne. Ce résultat général est appliqué au cas du plan et permet d'analyser de nouveaux algorithmes de triangulation de Delaunay plus performants que ceux connus à ce jour. Le principe sous-jacent est de diviser le domaine selon des arbres bidimensionnels (quadtree, 2d-tree, bucket-tree. . . ) puis de fusionner les cellules obtenues selon deux directions. On étudie actuellement la prise en compte de contraintes directement pendant la phase de triangulation avec des algorithmes de ce type. De nouveaux algorithmes pratiques de localisation dans une triangulation sont proposés, basés sur la randomisation à partir d'un arbre binaire de recherche dynamique de type AVL, dont l'un est plus rapide que l'algorithme optimal de Kirkpatrick, au moins jusqu'à 12 millions de sites K Nous travaillons actuellement sur l'analyse rigoureuse de leur complexité en moyenne. Ce nouvel algorithme est utilisé pour construire " en-ligne " une triangulation de Delaunay qui est parmi les plus performantes des méthodes " en-ligne " connues à ce jour.
Fichier principal
Vignette du fichier
1997_Lemaire_Christophe.pdf (2.94 Mo) Télécharger le fichier
Loading...

Dates et versions

tel-00850521 , version 1 (07-08-2013)

Identifiants

  • HAL Id : tel-00850521 , version 1

Citer

Christophe Lemaire. Triangulation de Delaunay et arbres multidimensionnels. Synthèse d'image et réalité virtuelle [cs.GR]. Ecole Nationale Supérieure des Mines de Saint-Etienne; Université Jean Monnet - Saint-Etienne, 1997. Français. ⟨NNT : 1997STET4021⟩. ⟨tel-00850521⟩
488 Consultations
2744 Téléchargements

Partager

Gmail Facebook X LinkedIn More