Thanks for pointing me to this! I had in the back of my mind that Aldous had surely considered a version of this problem but didn't think to check his open problem list. By the way, I imagine that $L_n$ is of order $n^{1/2}$ and not $n^{-1/2}$ ($L_n$ can't be smaller than the diameter of the cloud of points and therefore cannot tends to 0). I was also made aware of this work projecteuclid.org/… which seems relevant.