Explicit array-based compact data structures for triangulations: practical solutions with theoretical guarantees

Abstract : 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 maximal 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. Our data structures require linear construction time, and are fast decodable from a standard compressed format without using additional memory allocation. All bounds, concerning storage requirements and navigation performances, hold in the worst case. We have implemented and tested our results, and experiments confirm the practical interest of compact data structures.
Document type :
Reports
Complete list of metadatas

Cited literature [42 references]  Display  Hide  Download


https://hal.inria.fr/inria-00623762
Contributor : Olivier Devillers <>
Submitted on : Thursday, November 23, 2017 - 5:47:28 PM
Last modification on : Wednesday, April 3, 2019 - 1:23:05 AM

Files

RR-7736v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00623762, version 3

Citation

Luca Castelli Aleardi, Olivier Devillers. Explicit array-based compact data structures for triangulations: practical solutions with theoretical guarantees. [Research Report] RR-7736, INRIA. 2017, pp.39. ⟨inria-00623762v3⟩

Share

Metrics

Record views

713

Files downloads

239