Les structures de données triangulaires compactes

Théorie et implémentation

L'évolution des moyens d'acquisition et de stockage a produit une hausse des volumes utilisés pour stocker les objets géométriques.

La réduction des tailles de ces volumes fait l'objet de plusieurs disciplines qui visent à comprimer le volume au maximum, et élaborer des structures compactes qui minimisent la taille demandée.

Dans cette thèse, des solutions pratiques et compactes pour les triangulations sont présentées.

Pour ce faire, deux issues sont discutées: modifier la représentation interne en mémoire, et redéfinir les types abstraits des objets.

Une première solution consiste à utiliser des numéros sur une taille arbitraire de bits, au lieu des références absolues.

Une deuxième piste consiste à utiliser des catalogues stables et de représenter la triangulation comme un ensemble de paquets.

Une troisième solution consiste à décomposer la triangulation en plusieurs sous-triangulations permettant ainsi de coder les références dans une sous-triangulation sur un nombre réduit de bits.

Le présent livre s'adresse à tous les étudiants et chercheurs intéressés par la géométrie algorithmique et par les structures de données en général.