Take $n$ points uniformly in $[0,1] \times [0,1]$. Then pick uniformly $X_0$ one of these points as your starting point. Then let $X_1$ be the nearest neighbor of $X_0$, let $X_2$ be the nearest neighbor (not yet visited) of $X_1$ and so on. What can be said of the asymptotic of $X_n-X_{n-1}$ the length of the last crossed edge? What about the length of the longest crossed edge? I stumbled upon these kind of models in the area of environmental statistics where one tries to find clusters in a geographical dataset but I am not sure if this question is interesting.

Edit : Many more questions could be asked about this model : If one makes the model dynamic by adding the points in $[0,1]^2$ sequentially, most of the time the addition of an extra point changes the path only locally, but from time to time it will have a big impact. Does the path converges locally? (I guess not). How often do you see catastrophic modifications of the paths?

Finally, is there a way to find an interesting local spectrum in this object by renormalizing it and looking at the sizes of the edge ? It is probably related to the local dimension of the counting measure of the uniform PPP on [0,1]^2. But as pointed out in the answer below the first step would be to obtain the asymptotic of $L_n$ the total length.


1 Answer 1


This is closely related to a nice open problem of David Aldous, from the list of open problems on his web site, some version of which in fact has quite a long history in the combinatorial optimization community. At the above link Aldous has references to existing knowledge about the problem. The state of the art is that the sum of all edge lengths is $O(n^{1/2})$ in expectation.

  • $\begingroup$ 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. $\endgroup$ Nov 1, 2011 at 16:40
  • $\begingroup$ Sorry, you're right. That's what I get for commenting before my first coffee. I've corrected my response. Welcome to MO. $\endgroup$ Nov 1, 2011 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.