Succinct representation of triangulations with a boundary

L. Castelli Aleardi; Olivier Devillers; Gilles Schaeffer

doi:10.1007/11534273_13

Succinct representation of triangulations with a boundary

INRIA

Research output: Contribution to journal › Conference article › peer-review

Abstract

We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses matches the entropy of the class of structures represented. For the case of planar triangulations with a boundary we propose a succinct representation of the combinatorial information that improves to 2.175 bits per triangle the asymptotic amount of space required and that supports the navigation between adjacent triangles in constant time (as well as other standard operations). For triangulations with m faces of a surface with genus g, our representation requires asymptotically an extra amount of 36(g -1) Ig m bits (which is negligible as long as g ≪ m/1g m).

Original language	English
Pages (from-to)	134-145
Number of pages	12
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3608
DOIs	https://doi.org/10.1007/11534273_13
Publication status	Published - 1 Jan 2005
Event	9th International Workshop on Algorithms and Data Structures, WADS 2005 - Waterloo, Canada Duration: 15 Aug 2005 → 17 Aug 2005

Access to Document

10.1007/11534273_13

Cite this

@article{8b7cf4567f0747f28f64c33493b9d88b,

title = "Succinct representation of triangulations with a boundary",

abstract = "We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses matches the entropy of the class of structures represented. For the case of planar triangulations with a boundary we propose a succinct representation of the combinatorial information that improves to 2.175 bits per triangle the asymptotic amount of space required and that supports the navigation between adjacent triangles in constant time (as well as other standard operations). For triangulations with m faces of a surface with genus g, our representation requires asymptotically an extra amount of 36(g -1) Ig m bits (which is negligible as long as g ≪ m/1g m).",

author = "Aleardi, \{L. Castelli\} and Olivier Devillers and Gilles Schaeffer",

year = "2005",

month = jan,

day = "1",

doi = "10.1007/11534273\_13",

language = "English",

volume = "3608",

pages = "134--145",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

note = "9th International Workshop on Algorithms and Data Structures, WADS 2005 ; Conference date: 15-08-2005 Through 17-08-2005",

}

Succinct representation of triangulations with a boundary. / Aleardi, L. Castelli; Devillers, Olivier; Schaeffer, Gilles.
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 3608, 01.01.2005, p. 134-145.

Research output: Contribution to journal › Conference article › peer-review

TY - JOUR

T1 - Succinct representation of triangulations with a boundary

AU - Aleardi, L. Castelli

AU - Devillers, Olivier

AU - Schaeffer, Gilles

PY - 2005/1/1

Y1 - 2005/1/1

N2 - We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses matches the entropy of the class of structures represented. For the case of planar triangulations with a boundary we propose a succinct representation of the combinatorial information that improves to 2.175 bits per triangle the asymptotic amount of space required and that supports the navigation between adjacent triangles in constant time (as well as other standard operations). For triangulations with m faces of a surface with genus g, our representation requires asymptotically an extra amount of 36(g -1) Ig m bits (which is negligible as long as g ≪ m/1g m).

AB - We consider the problem of designing succinct geometric data structures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses matches the entropy of the class of structures represented. For the case of planar triangulations with a boundary we propose a succinct representation of the combinatorial information that improves to 2.175 bits per triangle the asymptotic amount of space required and that supports the navigation between adjacent triangles in constant time (as well as other standard operations). For triangulations with m faces of a surface with genus g, our representation requires asymptotically an extra amount of 36(g -1) Ig m bits (which is negligible as long as g ≪ m/1g m).

U2 - 10.1007/11534273_13

DO - 10.1007/11534273_13

M3 - Conference article

AN - SCOPUS:26844436915

SN - 0302-9743

VL - 3608

SP - 134

EP - 145

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 9th International Workshop on Algorithms and Data Structures, WADS 2005

Y2 - 15 August 2005 through 17 August 2005

ER -

Succinct representation of triangulations with a boundary

Abstract

Access to Document

Fingerprint

Cite this