Sharp phase transitions for k-fold coverage using Morse theory

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 k-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.