Skip to main content
2 of 7
deleted 2 characters in body
wolfies
  • 469
  • 3
  • 8

The question states asymptotic results, namely that as $n$ becomes large, the shortest path $L_n$ through $n$ points satisfies

$$L_n \to \sqrt{n} \beta \quad \text{ where } \quad \beta \approx 0.71~$$

Based on a quick play, what does seem clear is that the stated asymptotic result of $0.71 \sqrt{n}$ does, in fact, do a very poor job for your desired purpose, when $n$ is not large, or indeed even when $n$ is moderately large, such as $n= 50$.

The distribution of the shortest path through $n$ points

The following 3 diagrams plot the empirical distribution of the shortest path through $n$ points, when $n = 3, 20$ and 50 (each simulated 100,000 times). The vertical red line denotes $0.71 \sqrt{n}$ on each plot.

  • $n = 3$:
http://www.tri.org.au/se/nequal3plot.png
  • $n = 20$:
http://www.tri.org.au/se/nequal20plot.png
  • $n = 50$:
http://www.tri.org.au/se/nequal50plot.png

The following diagram compares:

  • Marks (1948) lower bound for the expected shortest path: $\sqrt{\frac{1}{2}} \left(\sqrt{n}-\frac{1}{\sqrt{n}}\right)$

  • Mahalanobis estimate of the expected shortest path: $\sqrt{n}-\frac{1}{\sqrt{n}}$

  • The actual expected shortest path [ round dots ]

  • The OP's stated asymptote: $.71 \sqrt{n}$

http://www.tri.org.au/se/mahalanobisetimateexpectedshortestpath.png
wolfies
  • 469
  • 3
  • 8