1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 2013 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, 2013 at 17:33

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

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.