Sharp Phase Transitions for k-Fold Coverage Using Morse Theory

2025/10/23 by Yohai Reani, Reani, Yohai, Omer Bobrowski +1
Mathematics · Computer Science · #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.2510.20329

Abstract

We introduce a novel approach for studying random k-coverage, using Morse theory for the k-nearest neighbor (k-NN) distance function. We prove a sharp phase transition for the number of critical points of the k-NN distance function, from which we conclude a phase transition for k-coverage. In addition, in the critical window our new framework enables us to prove a Poisson process approximation (in both location and size) for the last uncovered regions.

Citations

• Random coverage of a manifold with boundary
• On the rate of convergence in the Hall-Janson coverage theorem
• Morse Theory for the k-NN Distance Function
• Covering one point process with another
• Poisson process approximation under stabilization and Palm coupling
• Random Euclidean coverage from within
• Random Čech Complexes on Manifolds with Boundary
• Homological Connectivity in Random Čech Complexes
• Random Čech Complexes on Riemannian Manifolds
• On the Vanishing of Homology in Random Čech Complexes
• The Topology of Probability Distributions on Manifolds

Related

• Morse Theory for the k-NN Distance Function
• Distance Functions, Critical Points, and the Topology of Random Čech Complexes
• A local criterion of topological phase transitions
• Phase transition in random distance graphs on the torus
• Phase transition for the vacant set of random walk and random interlacements