Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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.) –  Ben Barber Nov 22 '13 at 16:07
    
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. –  wolfies Nov 22 '13 at 17:33

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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