On the metric distortion of nearest-neighbour graphs on random point sets

Amitabha Bagchi, Sohit Bansal

We study the graph constructed on a Poisson point process in $d$ dimensions by connecting each point to the $k$ points nearest to it. This graph a.s. has an infinite cluster if $k…