Data structure for efficient handling of quotient flag complexes
A data structure for quotient flag complexes
Computational GeometryData Structures and Algorithms
Summary
The paper explores how to store and manage special geometric shapes called flag complexes that have been simplified by shrinking certain parts to points. The authors find conditions under which the simplified shapes keep a nice ordering of their faces and identify which pieces of the shape are essential to keep track of. They introduce a new data structure called the QF-tree that efficiently stores these shapes after simplification. This new approach can save space and handle local updates better than older methods in certain cases.
What this means in practice
- •For topological data analysts: Represent and efficiently update quotient flag complexes in topological data analysis pipelines, improving memory use and local computations.
- •For computational geometers: Use the QF-tree data structure to store and manipulate quotient complexes arising from collapsing subcomplexes, facilitating complex geometric modeling.
Authors
Konstantin Sorokin, Aleksandr Levin, Maxim Beketov, Anton Ayzenberg
Abstract
Vietoris-Rips filtrations, which are standard in topological data analysis, are flag complexes, and a simplex tree stores these without any attaching data. In this paper we ask what survives of this economy when a flag complex $K$ is divided by a subcomplex $A$, each connected component of $A$ being crushed to a point. Such a quotient is a CW complex whose cells are the simplices of $K\setminus A$, but their attaching maps are no longer implicit. We show that for flag $K$ the face order of the quotient is strictly graded exactly when $A$ is flag, and that the surviving labelled cells are determined by those of dimension at most 3. For $m$-flag pairs the threshold is $2m+1$, and it drops to $m+2$ when $K$ is flag. The prescribed cells form a regular CW decomposition only when $A$ is full in $K$. These results justify the QF-tree: a cell table that stores, for each surviving simplex, its ordered list of $d+1$ facets with collapsed facets flagged, indexed by a trie of quotient-vertex words. For bounded dimension its size is linear in the number of surviving simplices plus the retained provenance, and we derive and verify a simple formula for the collapsed fraction above which it is smaller than the homotopy-equivalent cone model. Because a collapse changes the attaching data only on the closed star of $A$, the QF-tree can also be applied locally inside a simplex tree. For a ball-shaped $A$ in the sampled Vietoris--Rips regime the closed star is a thin shell, and the median compact budget is below the cone model at every sampled radius. An accompanying library, modelled on Gudhi, implements the QF-tree, its local variant, an editable layer with local quotient updates, gluing, disc attachment, induced maps, cup products, fundamental-group presentations and zigzag persistence, and provided experiments separate the cost of maintaining a quotient from the cost of the algebra computed on it.