Abstract
The Delaunay filtration D•(X) of a point cloud X ⊂ Rd 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 (equation presented), 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 (equation presented). Our implementation, based on CGAL, computes DC•(γ) with modest overhead compared to computing D•(X), and handles tens of thousands of points in R3 within seconds.
Originalsprache | englisch |
---|---|
Titel | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
Herausgeber (Verlag) | Association of Computing Machinery |
Seiten | 4872-4891 |
Seitenumfang | 20 |
DOIs | |
Publikationsstatus | Veröffentlicht - 2024 |
Veranstaltung | 35th Annual ACM-SIAM Symposium on Discrete Algorithms: SODA 2024 - Alexandria, USA / Vereinigte Staaten Dauer: 7 Jan. 2024 → 10 Jan. 2024 |
Konferenz
Konferenz | 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Kurztitel | SODA 2024 |
Land/Gebiet | USA / Vereinigte Staaten |
Ort | Alexandria |
Zeitraum | 7/01/24 → 10/01/24 |
ASJC Scopus subject areas
- Software
- Allgemeine Mathematik