LIX Ecole PolytechniqueGeometrica INRIA Sophia

Luca Castelli

Description

Niveau: Supérieur, Doctorat, Bac+8
Luca Castelli Aleardi LIX Ecole PolytechniqueGeometrica - INRIA Sophia Soutenance de these, 12 decembre 2006, LIX Representations compactes de structures de donnees geometriques

• disque dur


• structures de donnees geometriques


• representations compactes de structures


• statue du david


• donnees structurees de nature geometrique


• explosion de la taille des donnees


• modelisation geometrique

Sujets

• Castelli
• Disque dur
• Modélisation géométrique

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 décembre 2006
• Nombre de lectures: 63
• Poids de l'ouvrage: 2 Mo

Extrait

Repr´esentations compactes de structures
de donn´ees g´eom´etriques
Soutenance de th`ese, 12 d´ecembre 2006, LIX
Luca Castelli Aleardi
´Geometrica - INRIA Sophia LIX Ecole PolytechniqueLe domaine de rechercheDonn´ees structur´ees de nature g´eom´etrique
Triangulations et graphes maillages surfaciques maillages volumiques
Domaines d’application
Mod´elisation g´eom´etriqueRecontruction
de surfaces GIS TechnologyMasses de donn´ees
L’explosiondelatailledesdonn´eesposedespbsdetraitement
Statue de St. Matthieu (Stanford’s Digital
Michelangelo Project, 2000)
186 million de sommets
6 Giga octets (stockage sur disque)
dizaines de minutes (temps pour la lecture
de disque dur)
Statue du David (Stanford’s Digital
Michelangelo Project, 2000)
2 milliards de polygons
32 Giga octets (sans compression)
Pas d’algorithme et structure de
donn´ees pouvant traiter le mod`ele
tout entierTh`emes de recherche
Compression de maillages
Structures de donn´ees g´eom´etriques
Transmission sur r´eseau
Stockage
Repr´esentations compactes d’objets g´eom´etriques
i
...Repr´esentations compactesUn exemple: arbres binaires et ordonn´es
arbre ordonn´e `a n arˆetes
mot de parenth`eses ´equilibibrr´´ee
1110100010110100
⇒ 2n bits pour coder un arbre avec n arˆetes.
´Enum´eration des arbres plans avec n arˆetes.

32n1 2n −
2kB k = ≈ 2 nn n+1 nUn exemple: arbres binaires et ordonn´es
arbre ordonn´e `a n arˆetes
mot de parenth`eses ´equilibibrr´´ee
1110100010110100
⇒ 2n bits pour coder un arbre avec n arˆetes.
Ce codage est ”asymptotiquement optimal”.
• le coutˆ m´emoire d’un objet correspond asymptotique-
ment `a l’entropie de la classe;
log kB k = 2n+O(lgn)2 nUn exemple: arbres binaires et ordonn´es
Le code de contour d’un arbre plan (arbre ordonn´e).
arbre ordonn´e `a n arˆetes
mot de parenth`eses ´equilibibrr´´ee
1110100010110100
⇒ 2n bits pour coder un arbre avec n arˆetes.
maisnepermetpasderepondreefficacement`adesrequˆetesd’adjacenceUn exemple: arbres binaires et ordonn´es
Repr´esentation explicite par pointeurs
lgnlgn
lgn lgnparent parent
/
lgn
parent
parent parent
/ / / /
parent parent
/ / / /
il est possible de tester en temps O(1) l’adjacence entre sommets
ce codage n’est pas optimal: il faut Θ(nlgn) bits