Delaunay Bifiltrations of Functions on Point Clouds

Abstract

The Delaunay filtration ${\mathcal{D}}_{\bullet }(X)$ of a point cloud $X\subset {\mathbb{R}}^d$ is a central tool of computational topology. Its use is justified by the topological equivalence of ${\mathcal{D}}_{\bullet }(X)$ and the offset (i.e., union-of-balls) filtration of $X$. Given a function $\gamma :X\to \mathbb{R}$, we introduce a Delaunay bifiltration ${\mathcal{D}\mathcal{C}}_{\bullet }(\gamma )$ that satisfies an analogous topological equivalence, ensuring that ${\mathcal{D}\mathcal{C}}_{\bullet }(\gamma )$ topologically encodes the offset filtrations of all sublevel sets of $\gamma$, as well as the topological relations between them. ${\mathcal{D}\mathcal{C}}_{\bullet }(\gamma )$ is of size $O(|X{|}^{\lceil \frac{d+1}{2}\rceil })$, which for $d$ odd matches the worst-case size of ${\mathcal{D}}_{\bullet }(X)$. Adapting the Bowyer-Watson algorithm for computing Delaunay triangulations, we give a simple, practical algorithm to compute ${\mathcal{D}\mathcal{C}}_{\bullet }(\gamma )$ in time $O(|X{|}^{\lceil \frac{d}{2}\rceil +1})$. Our implementation, based on CGAL, computes ${\mathcal{D}\mathcal{C}}_{\bullet }(\gamma )$ with modest overhead compared to computing ${\mathcal{D}}_{\bullet }(X)$, and handles tens of thousands of points in ${\mathbb{R}}^3$ within seconds.

28 pages, 7 figures, 8 tables. To appear in the proceedings of SODA24