Sharp phase transitions for k-fold coverage using Morse theory

Abstract: The study of random k-fold coverage explores when every point in a “big set” is covered by at least k “small sets” whose centres are randomly placed. This problem arises in many fields, with applications in wireless networks, sensor deployment, stochastic geometry etc. Motivated by advances in the field of random topology, in this talk we introduce a novel analysis of k-fold coverage processes using the k-nearest neighbor (kNN) distance function, whose sublevel sets are the 𝑘-fold covers. This talk has two parts. Firstly, we provide an adaptation of Morse theory to the kNN distance function, showing that its critical points are the sole obstructions for k-fold coverage. Moreover, we provide a combinatorial description of these critical points, and their effect on the k-fold covers’ topology. Secondly, in the probabilistic setting where centres are generated by a homogeneous Poisson point process, we prove phase transitions for the vanishing of critical points, compute the threshold for k-fold coverage, and prove a Poisson process approximation (in both location and size) for the last uncovered regions.