# Expected length of the shortest polygonal chain connecting N random points in the unit square

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?

• 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) 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.
I do not think that the value of $c$ is known explicitly.