Approximation of the multicover bifiltration

For a finite point set P $\subset{R^d}$, let $M_{r,k}$ denote the set of points in $R^d$ that are within distance r of at least k points in P. Allowing r and k to vary yields a 2-parameter family of spaces M, called the multicover bifiltration of P. It is a density-sensitive extension of the union-of-balls filtration commonly considered in TDA. It is robust to outliers in a strong sense, which motivates the problem of efficiently computing it (up to homotopy). A recent algorithm of Edelsbrunner and Osang computes a polyhedral model of M called the rhomboid bifiltration. In this work, we introduce an approximation of M (up to homotopy) which extends a version of the rhomboid tiling and devise an efficient algorithm to compute it.

The talk is based on joint work with Uli Bauer, Tamal Dey and Michael Lesnick.