Skip to main content
Corrected some incorrect math.
Source Link

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, so in particular the length of the last edge crossed and of the longest crossed edge are both at most $O(n^{-1/2})$$O(n^{1/2})$ in expectation. A corresponding lower bound should certainly be true, and is trivial for the longest crossed edge (there are points whose nearest neighbour is distance $\Theta(n^{-1/2})$ away). I don't see an easy argument for a lower bound for the length of the last edge, though.

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, so in particular the length of the last edge crossed and of the longest crossed edge are both at most $O(n^{-1/2})$ in expectation. A corresponding lower bound should certainly be true, and is trivial for the longest crossed edge (there are points whose nearest neighbour is distance $\Theta(n^{-1/2})$ away). I don't see an easy argument for a lower bound for the length of the last edge, though.

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.

Source Link

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, so in particular the length of the last edge crossed and of the longest crossed edge are both at most $O(n^{-1/2})$ in expectation. A corresponding lower bound should certainly be true, and is trivial for the longest crossed edge (there are points whose nearest neighbour is distance $\Theta(n^{-1/2})$ away). I don't see an easy argument for a lower bound for the length of the last edge, though.