Bifunction and Interlevel Delaunay Trifiltrations
This provides a new topological tool for analyzing time-varying data, extending prior 2-parameter filtrations to three parameters.
The authors introduce a 3-parameter extension of the Delaunay filtration for point clouds with an ℝ²-valued function, proving weak equivalence to the offset filtration. Their algorithm computes this trifiltration in O(|X|^{⌈d/2⌉+2}) time and handles thousands of points in ℝ³ with near-linear memory growth.
A key property of the Delaunay filtration is that it is topologically (i.e., weakly) equivalent to the offset (union-of-balls) filtration. Recently, this filtration has been extended to point clouds equipped with an $\mathbb{R}$-valued function, yielding a computable 2-parameter filtration that satisfies an analogous weak equivalence. Motivated in part by the study of time-varying data, we introduce a 3-parameter extension of the Delaunay filtration for point clouds equipped with an $\mathbb{R}^2$-valued function, also satisfying an analogous weak equivalence. For a point cloud $X \subset \mathbb{R}^d$, our trifiltration has size $O\bigl(|X|^{\lceil(d+1)/2\rceil+1}\bigr)$. We present an algorithm that computes this trifiltration in time $O\bigl(|X|^{\lceil d/2\rceil+2}\bigr)$, together with an implementation. Our experiments demonstrate that implementation can handle thousands of points in $\mathbb{R}^3$, with memory growth that is nearly linear.