N points are selected uniformly at random in the unit square. Let L(N) be the expected length of the shortest (possibly self-intersecting) polygonal chain connecting all the points. It can be proved that $L(N)\sim c\sqrt{AN}$, for some constant $c$, where A is the area of the region (in our case A=1). Heuristics suggests c around 0.7, is there known an exact value for the constant c?

The question including some others was asked originally on math.SE, where some partial results where achieved.

If instead of a polygonal chain, we use the minimal spanning tree, a similar argument yields the same asymptotic formula, is the constant c known for this version?

  • 1
    $\begingroup$ I didn't see the word "Talagrand" in the math.SE thread, so I'll mention that $L(N)$ is tightly concentrated near $c\sqrt N$. I believe the precise value of the constant remains unknown. (Edit: all of this applies to the minimal spanning tree too.) $\endgroup$ – Ben Barber Nov 22 '13 at 16:07
  • $\begingroup$ OP wrote: The question was originally asked on math.SE. .... Not quite. The question posed on math.SE is about $n$ Uniformly random points on a disc of unit radius (i.e. of area $\pi$). The question here is about Uniformly random points on a unit square. $\endgroup$ – wolfies Nov 22 '13 at 17:33

Some partial answers:

1) The fact that the length is asymptotic to $c\sqrt{N}$ follows from sub-additivity.

2) This is the ``random travelling salesman'' problem. Joe Yukich wrote several papers on it and its variants.

3) See also the wikipedia page http://en.wikipedia.org/wiki/Travelling_salesman_problem#TSP_path_length_for_random_pointset_in_a_square

I do not think that the value of $c$ is known explicitly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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