Computing the Multicover Bifiltration
Open Access
- 20 February 2023
- journal article
- research article
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 70 (2) , 376-405
Abstract
Given a finite set $$A\subset {\mathbb {R}}^d$$ , let $$\text {Cov}_{r,k}$$ denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.
Keywords
Funding Information
- Austrian Science Fund (P 29984-N35, P 29984-N35, W1230, W1230)
- Marshallplan-Jubiläumsstiftung
- Brummer & Partners MathDataLab
This publication has 38 references indexed in Scilit:
- Scalar Field Analysis over Point Cloud DataDiscrete & Computational Geometry, 2011
- The Theory of Multidimensional PersistenceDiscrete & Computational Geometry, 2009
- Stability of Persistence DiagramsDiscrete & Computational Geometry, 2006
- Computing Persistent HomologyDiscrete & Computational Geometry, 2004
- The Meataxe as a tool in computational group theory1998
- The union of balls and its dual shapeDiscrete & Computational Geometry, 1995
- Homotopy Theories and Model Categories1995
- Power Diagrams: Properties, Algorithms and ApplicationsSIAM Journal on Computing, 1987
- Voronoi diagrams and arrangementsDiscrete & Computational Geometry, 1986
- Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs.Journal für die reine und angewandte Mathematik (Crelles Journal), 1908