Delaunay de données volumineuses

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.
Pour un objectif un peu plus pragmatique, disons que à l'heure actuelle, il hors de questions de dépasser quelques millions de points et que nous cherchons à passer à quelques centaines de millions pour un coût linéaire en temps en utilisant un stockage sur disque des points et de la triangulation.
Un sujet connexe est celui de l'optimisation en mémoire des structures de données pour représenter une triangulation, par exemple l'utilisation d'une certaine localité pour l'indexation des tétrahèdres ou des sommets devrait permettre d'utiliser des index occupant monis de mémoire que des pointeurs classiques.