16
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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$
    – Julien Berestycki
    Commented 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$
    – Louigi Addario-Berry
    Commented Nov 1, 2011 at 23:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .