The k-cover of a point cloud X in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathbb {R}^{d}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation> at radius r is the set of all points within distance r of at least k points of X. By varying r and k we obtain a two-parameter filtration known as the multicover bifiltration. This bifiltration has received attention recently because it is choice-free and robust to outliers. However, it is hard to compute: the smallest known equivalent simplicial bifiltration has <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(|X|^{d+1})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo stretchy="false">|</mo> <mi>X</mi> <msup> <mo stretchy="false">|</mo> <mrow> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> simplices. We introduce a <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$(1+\varepsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>ε</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximation of the multicover bifiltration of linear size <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(|X|)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo stretchy="false">|</mo> <mi>X</mi> <mo stretchy="false">|</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, for fixed d and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation>. The methods also apply to the subdivision Rips bifiltration on metric spaces of bounded doubling dimension, yielding analogous results.

A Sparse Multicover Bifiltration of Linear Size

期刊论文
发表日期：

2026年8月4日

查看全文

Ángel Javier Alonso

摘要

The k-cover of a point cloud X in $\mathbb {R}^{d}$ $R^{d}$ at radius r is the set of all points within distance r of at least k points of X. By varying r and k we obtain a two-parameter filtration known as the multicover bifiltration. This bifiltration has received attention recently because it is choice-free and robust to outliers. However, it is hard to compute: the smallest known equivalent simplicial bifiltration has $O(|X|^{d+1})$ $O (| X |^{d + 1})$ simplices. We introduce a $(1+\varepsilon )$ $(1 + ε)$ -approximation of the multicover bifiltration of linear size $O(|X|)$ $O (| X |)$ , for fixed d and $\varepsilon $ $ε$ . The methods also apply to the subdivision Rips bifiltration on metric spaces of bounded doubling dimension, yielding analogous results.