Rectification of interleavings and a persistent Whitehead theorem

Journal article

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{DC}_{\bullet}(\gamma)$ that satisfies an analogous topological equivalence, ensuring that $\mathcal{DC}_{\bullet}(\gamma)$ topologically encodes the offset filtrations of all sublevel sets of $\gamma$, as well as the topological relations between them. $\mathcal{DC}_{\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{DC}_{\bullet}(\gamma)$ in time $O(|X|^{\lceil \frac{d}{2}\rceil +1})$. Our implementation, based on CGAL, computes $\mathcal{DC}_{\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.Comment: 28 pages, 7 figures, 8 tables. To appear in the proceedings of SODA2

Authors: Lanari, E; Scoccola, L

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Mathematical Sciences Publishers
• Journal: Algebraic & Geometric Topology
• Volume: 23
• Issue: 2
• Pages: 803-832
• Publication date: 2023-05-09
• DOI: 10.2140/agt.2023.23.803
• ISSN: 1472-2739
• Language: English
• Keywords: n-connected; Homotopy sphere; Mathematics; Whitehead theorem; Homotopy group; Interleaving; Discrete mathematics; Homotopy; Pure mathematics; Invariant (physics); Fibration; Morphism; Combinatorics; Eilenberg–MacLane space; Conjecture; Computer science