Sharp Phase Transitions for k-Fold Coverage Using Morse Theory

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.