The shortest path through many points

作者：Jillian Beardwood, John H. Halton, J. M. Hammersley · 发表于：Mathematical Proceedings of the Cambridge Philosophical Society · 年份：1959 · DOI：10.1017/s0305004100034095 · 被引用次数：963 · 研究领域：Computational Geometry and Mesh Generation、Urban Design and Spatial Analysis、Transportation Planning and Optimization

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.