Building efficient and compact data structures for simplicial complexes

DOI10.4230/LIPICS.SOCG.2015.642MaRDI QIDQ5368718zbMATH OpenOpenAlexFDO

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

Publication date 10 October 2017

Full work available at URL https://arxiv.org/abs/1503.07444

zbMATH Keywords

compact data structuresminimal simplex automatonNP-hardnesssimplicial complex

Mathematics Subject Classification ID

General topology of complexes (57Q05) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

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 Simplex Tree while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree (MxST) and the Simplex Array List (SAL). We analyze the compressed Simplex Tree, the Maximal Simplex Tree, and the Simplex Array List under various settings.

Recommendations

• Building efficient and compact data structures for simplicial complexes
• A representation for abstract simplicial complexes: an analysis and a comparison.
• An efficient representation for filtrations of simplicial complexes

Cited in

(7)

• Building efficient and compact data structures for simplicial complexes
• Succinct and Implicit Data Structures for Computational Geometry
• Explicit Array-Based Compact Data Structures for Triangulations
• An efficient representation for filtrations of simplicial complexes
• The implementation of the colored abstract simplicial complex and its application to mesh generation
• A representation for abstract simplicial complexes: an analysis and a comparison.
• On the complexity of the representation of simplicial complexes by trees

Describes a project that uses

Uses Software

• Gudhi

This page was built for publication: Building efficient and compact data structures for simplicial complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368718)