The shortest path through many points

Publisher Website
Google Scholar
Abstract
We prove that the length of the shortest closed path throughnpoints in a bounded plane region of areavis ‘almost always’ asymptotically proportional to √(nv) for largen; and we extend this result to bounded Lebesgue sets ink–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 ofk; and we estimate the constant in the particular casek= 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.

This publication has 11 references indexed in Scilit: