Delaunay Bifiltrations of Functions on Point Clouds

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