Building Efficient and Compact Data Structures for Simplicial Complexes

Jean Daniel Boissonnat; C. S. Karthik; Sébastien Tavenas

doi:10.1007/s00453-016-0207-y

Building Efficient and Compact Data Structures for Simplicial Complexes

Jean Daniel Boissonnat, C. S. Karthik, Sébastien Tavenas

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the ST while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree and the Simplex Array List. We analyze the compressed ST, the Maximal Simplex Tree, and the Simplex Array List under various settings.

Original language	English (US)
Pages (from-to)	530-567
Number of pages	38
Journal	Algorithmica
Volume	79
Issue number	2
DOIs	https://doi.org/10.1007/s00453-016-0207-y
State	Published - Oct 1 2017
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science(all)
Computer Science Applications
Applied Mathematics

Keywords

Automaton
Compact data structures
NP-hard
Simplicial complex

Access to Document

10.1007/s00453-016-0207-y

Cite this

@article{2afb9542d120462db011667d1d20ae1a,

title = "Building Efficient and Compact Data Structures for Simplicial Complexes",

abstract = "The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the ST while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree and the Simplex Array List. We analyze the compressed ST, the Maximal Simplex Tree, and the Simplex Array List under various settings.",

keywords = "Automaton, Compact data structures, NP-hard, Simplicial complex",

author = "Boissonnat, {Jean Daniel} and Karthik, {C. S.} and S{\'e}bastien Tavenas",

note = "Funding Information: Karthik C. S.: This work was partially supported by Irit Dinur{\textquoteright}s ERC-StG Grant Number 239985. Some parts of this work were done at ENS Lyon and at University of Nice - Sophia Antipolis, and were supported by LIP fellowship and Labex UCN@Sophia scholarship respectively. Funding Information: J.-D. Boissonnat: This work was partially supported by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions). Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2017",

month = oct,

day = "1",

doi = "10.1007/s00453-016-0207-y",

language = "English (US)",

volume = "79",

pages = "530--567",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Building Efficient and Compact Data Structures for Simplicial Complexes

AU - Boissonnat, Jean Daniel

AU - Karthik, C. S.

AU - Tavenas, Sébastien

N1 - Funding Information: Karthik C. S.: This work was partially supported by Irit Dinur’s ERC-StG Grant Number 239985. Some parts of this work were done at ENS Lyon and at University of Nice - Sophia Antipolis, and were supported by LIP fellowship and Labex UCN@Sophia scholarship respectively. Funding Information: J.-D. Boissonnat: This work was partially supported by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions). Publisher Copyright: © 2016, Springer Science+Business Media New York.

PY - 2017/10/1

Y1 - 2017/10/1

N2 - The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the ST while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree and the Simplex Array List. We analyze the compressed ST, the Maximal Simplex Tree, and the Simplex Array List under various settings.

AB - The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the ST while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree and the Simplex Array List. We analyze the compressed ST, the Maximal Simplex Tree, and the Simplex Array List under various settings.

KW - Automaton

KW - Compact data structures

KW - NP-hard

KW - Simplicial complex

UR - http://www.scopus.com/inward/record.url?scp=84986300474&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84986300474&partnerID=8YFLogxK

U2 - 10.1007/s00453-016-0207-y

DO - 10.1007/s00453-016-0207-y

M3 - Article

AN - SCOPUS:84986300474

SN - 0178-4617

VL - 79

SP - 530

EP - 567

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -

Building Efficient and Compact Data Structures for Simplicial Complexes

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this