The shortest path through many points

TLDR

The results may generalize to Plateau's problem and Douglas' problem. The study proves that the length of the shortest closed path through \(n\) points in a bounded plane region of area \(v\) is asymptotically proportional to \(\sqrt{nv}\) for large \(n\), and extends this to \(k\)-dimensional Euclidean space. The authors provide numerical bounds for the proportionality constants across dimensions and estimate the constant for \(k=2\). The proportionality constants depend only on dimensionality, not on region shape, and the findings relate to the traveling‑salesman, Steiner, and Loberman–Weinberger problems.

Abstract

ABSTRACT We prove that the length of the shortest closed path through n points in a bounded plane region of area v is ‘almost always’ asymptotically proportional to √( nv ) for large n ; and we extend this result to bounded Lebesgue sets in k –dimensional Euclidean space. The constants of proportionality depend only upon the dimensionality of the space, and are independent of the shape of the region. We give numerical bounds for these constants for various values of k ; and we estimate the constant in the particular case k = 2. The results are relevant to the travelling-salesman problem, Steiner's street network problem, and the Loberman—Weinberger wiring problem. They have possible generalizations in the direction of Plateau's problem and Douglas' problem.