Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T15:56:46.289Z Has data issue: false hasContentIssue false

The shortest path through many points

Published online by Cambridge University Press:  24 October 2008

Jillian Beardwood
Affiliation:
St Hugh's CollegeOxford
J. H. Halton
Affiliation:
Balliol CollegeOxford
J. M. Hammersley
Affiliation:
Trinity CollegeOxford
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1959