Delaunay de données volumineuses

Lieu :
INRIA , Unité de Sophia Antipolis
Projet Geometrica
BP 93
06902 Sophia Antipolis
FRANCE

Information:
Olivier Devillers - Chargé de recherche
Projet Geometrica
Tel : +33 4 92 38 77 63
e-mail: <Olivier.Devillers(at)sophia.inria.fr>
Description:
L'évolution des capacités de stockage et de numérisation rendent les volumes de données à traiter de plus en plus importants. Le calcul de la triangulation de Delaunay de millions de points en trois dimensions deviens nécessaire, par exemple pour des applications en reconstruction de surface. La triangulation de Delaunay est calculée efficacement par des méthodes incrémentales randomisées dans lesquelles les points sont insérés dans un ordre aléatoire. Malheureusement, insérer les points dans un ordre aléatoire sollicite fortement le swap et rend ces algorithmes inutilisable lorsque la mémoire vive est saturée.

Le but de ce stage est de déterminer des ordres suffisamment aléatoires pour ne pas altérer les performances des algorithmes randomisés, mais permettant de moins solliciter le swap. On cherchera à démontrer l'efficacité de ces ordres tant du point de vue théorique par des calculs de complexité que du point de vue pratique par l'implantation et l'expérimentation sur des données réelles.

Mots clefs :
Géométrie Algorithmique.


Outils :
PC Linux,
langage C++,
Bibliothèque géométrique CGAL


Références :
Nina Amenta and Sunghee Choi Blocked randomized incremental constructions UT Technical Report Number TR-02-54, 2002. http://www.cs.utexas.edu/users/amenta/pubs/insertionTech.pdf
Olivier Devillers and Philippe Guigue. The shuffling buffer. Internat. J. Comput. Geom. Appl., 11:555--572, 2001. http://www.inria.fr/rrrt/rr-3988.html


Retour aux autres stages

Olivier Devillers
Last modified: Tue Jan 29 08:47:22 MET 2002