La hiérarchie de Delaunay, une structure pour le calcul de la triangulation de Delaunay.


Nous proposons une nouvelle structure de donnée pour le calcul de la triangulation de Delaunay de points du plan permettant de combiner simultanément : une bonne complexité théorique dans le cas le pire, un très bon comportement pratique et une occupation mémoire réduite. Cette structure permet également une mise à jour dynamique (insertions et suppressions).

La structure de localisation utilisée comporte plusieurs niveaux. Au niveau le plus bas contient la triangulation de Delaunay de tous les points, ensuite chaque niveau contient la triangulation d'un echantillon aléatoire des points du niveau précédent. La localisation d'un nouveau point est effectuée en marchant dans une triangulation afin de déterminer le plus proche voisin du nouveau point à ce niveau ; puis la marche reprends à partir de ce voisin au niveau inférieur. L'utilisation d'échantillon assez petit (3 %) garanti un faible coût mémoire ; la marche et l'utilisation du plus proche voisin pour changer de niveau une convergence rapide pour localiser la requète.

La suppression est implémenté par dualité avec l'enveloppe convexe 3D en utilisant un effeuillage (shelling) partiel.


Pour une implémentation efficace découlant de ces travaux, utiliser la hierarchie de Delaunay dans CGAL

FTP site.


Last modified: Tue Jan 17 11:07:47 CET 2006 Olivier Devillers Logiciels Accueil PRISME same page in english