2023/10/24 by Ángel Javier Alonso, Michael Kerber, Alonso, Ángel Javier +5 · 2 citations
Computer Science · #Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2310.15902
openalex publication_date 2023/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Delaunay filtration D\bullet(X) of a point cloud X⊂ ℝd is a central tool of computational topology. Its use is justified by the topological equivalence of D\bullet(X) and the offset (i.e., union-of-balls) filtration of X. Given a function γ: X → ℝ, we introduce a Delaunay bifiltration DC\bullet(γ) that satisfies an analogous topological equivalence, ensuring that DC\bullet(γ) topologically encodes the offset filtrations of all sublevel sets of γ, as well as the topological relations between them. DC\bullet(γ) is of size O(|X|\lceil(d+1)/(2)\rceil), which for d odd matches the worst-case size of D\bullet(X). Adapting the Bowyer-Watson algorithm for computing Delaunay triangulations, we give a simple, practical algorithm to compute DC\bullet(γ) in time O(|X|\lceil (d)/(2)\rceil +1). Our implementation, based on CGAL, computes DC\bullet(γ) with modest overhead compared to computing D\bullet(X), and handles tens of thousands of points in ℝ3 within seconds.