TY - GEN
T1 - Explicit array-based compact data structures for triangulations
AU - Castelli Aleardi, Luca
AU - Devillers, Olivier
PY - 2011/12/26
Y1 - 2011/12/26
N2 - We consider the problem of designing space efficient solutions for representing triangle meshes. Our main result is a new explicit data structure for compactly representing planar triangulations: if one is allowed to permute input vertices, then a triangulation with n vertices requires at most 4n references (5n references if vertex permutations are not allowed). Our solution combines existing techniques from mesh encoding with a novel use of minimal Schnyder woods. Our approach extends to higher genus triangulations and could be applied to other families of meshes (such as quadrangular or polygonal meshes). As far as we know, our solution provides the most parsimonious data structures for triangulations, allowing constant time navigation in the worst case. Our data structures require linear construction time, and all space bounds hold in the worst case. We have implemented and tested our results, and experiments confirm the practical interest of compact data structures.
AB - We consider the problem of designing space efficient solutions for representing triangle meshes. Our main result is a new explicit data structure for compactly representing planar triangulations: if one is allowed to permute input vertices, then a triangulation with n vertices requires at most 4n references (5n references if vertex permutations are not allowed). Our solution combines existing techniques from mesh encoding with a novel use of minimal Schnyder woods. Our approach extends to higher genus triangulations and could be applied to other families of meshes (such as quadrangular or polygonal meshes). As far as we know, our solution provides the most parsimonious data structures for triangulations, allowing constant time navigation in the worst case. Our data structures require linear construction time, and all space bounds hold in the worst case. We have implemented and tested our results, and experiments confirm the practical interest of compact data structures.
KW - Schnyder woods
KW - compact representations
KW - graph encoding
KW - mesh data structures
KW - triangulations
UR - https://www.scopus.com/pages/publications/84055217318
U2 - 10.1007/978-3-642-25591-5_33
DO - 10.1007/978-3-642-25591-5_33
M3 - Conference contribution
AN - SCOPUS:84055217318
SN - 9783642255908
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 312
EP - 322
BT - Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
T2 - 22nd International Symposium on Algorithms and Computation, ISAAC 2011
Y2 - 5 December 2011 through 8 December 2011
ER -