Représentation succinte de triangulations

Luca Castelli Aleardi (LIX)

Résumé:

Nous considérons le problème de représenter des structures géométriques de manière compacte en gardant une implémentation efficace des opérations de navigation.

Pour le cas des triangulations à m faces, nous avons proposé une représentation succinte de l'information combinatoire qui nécéssite asymptotiquement de 2.175 bits par triangle et qui permet la navigation entre triangles adjacents en temps constant (résultat presenté à WADS 2005). Notre structure améliore les précédentes représentations compactes, étant optimale pour la classe des triangulations planaires avec un bord. Pour les triangulations à m faces d'une surface de genre g, notre représentation nécessite asymptotiquement de 36(g-1)log m bits supplémentaires.

Dans un autre travail (presenté à CCCG 2005), nous avons montré comment modifier notre codage, afin de permettre des opérations de mise à jour locale efficace de la triangulation. En particulier, il est possible de gérer l'insertion de sommets de degré trois en temps constant amorti, la suppression de sommets et le flip d'arête en temps O(log2m) amorti. La structure permet aussi l'accès en temps constant des informations associées aux sommets, notamment leurs coordonnées, cependant nous ne traitons pas ici la compression de cette information géométrique.

Nous envisageons aussi d'améliorer notre représentation afin d'obtenir un codage succint optimal pour la classe des triangulations planaires sans bord et la classe des graphes planaires 3-connexes.

(travail en collaboration avec Olivier Devillers et Gilles Schaeffer)