Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-09T08:37:21.715Z Has data issue: false hasContentIssue false
  • English
  • Français

The shortest path through many points

Published online by Cambridge University Press:  24 October 2008

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

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.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 55 , Issue 4 , October 1959 , pp. 299 - 327
Copyright
Copyright © Cambridge Philosophical Society 1959

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Borůvka, O.On a minimal problem. Práce Moravské Pridovedecké Spolecnosti 3 (1926).Google Scholar
(2)Courant, R. and Robbins, H.What is mathematics? (Oxford, 1941).Google Scholar
(3)Courant, R. and Schiffer, M.Dirichlet's principle, conformed mapping, and minimal surfaces. (New York, 1950).Google Scholar
(4)Dantzig, G., Fulkerson, R. and Johnson, S.Solution of a large-scale traveling salesman problem. J. Oper. Res. Soc. Amer. 2 (1954), 393–410.Google Scholar
(5)Douglas, J.Minimal surfaces of higher topological structure. Ann. Math., Princeton, 40 (1939), 205–98.CrossRefGoogle Scholar
(6)Erdélyi, A., Magnus, W., Oberhettinger, F. and Tricomi, F. G.Tables of integral transforms. Vol. I. (New York, 1954).Google Scholar
(7)Flood, M. M.The traveling salesman problem. J. Oper. Res. Soc. Amer. 4 (1956), 61–75.Google Scholar
(8)Ghosh, H. W.Expected travel among random points. Bull. Calcutta Statist. Ass. 2 (1948), 83–7.CrossRefGoogle Scholar
(9)Halmos, P. R.Measure theory. (New York, 1950).CrossRefGoogle Scholar
(10)Hardy, G. H.Divergent series. (Oxford, 1949).Google Scholar
(11)Heller, I.On the traveling salesman's problem. Part I. Basic Facts. George Washington Univ. Logistic Res. Project. (1954).Google Scholar
(12)Heller, I. On the traveling salesman's problem. Proc. Symp. Linear Programming. (Washington, 1955), 643–65.Google Scholar
(13)Holmes, H. S.Telegraph hand delivery. P.O. Telecomm. J. 9 (1957), 66–71.Google Scholar
(14)Jahnke, E. and Emde, F.Tables of functions with formulae and curves. 4th ed. (New York, 1945).Google Scholar
(15)Jessen, R. J.Statistical investigation of a sample farm survey. Bull. Iowa St. Coll. Agric. Res. 304 (1942).Google Scholar
(16)Kruskal, J. B.On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7 (1956), 48–50.CrossRefGoogle Scholar
(17)Loberman, H. and Weinberger, A.Formal processes for connecting terminals with a minimum total wire length. J. Ass. Comp. Machy. 4 (1957), 428–37.CrossRefGoogle Scholar
(18)Mahalanobis, P. C.A sample survey of the acreage under jute in Bengal. Sankhyā, 4 (1940), 511–31.Google Scholar
(19)Marks, E. S.A lower bound for the expected travel among m random points. Ann. Math. Statist. 19 (1948), 419–22.CrossRefGoogle Scholar
(20)Morton, G. and Land, A. H.A contribution to the travelling-salesman problem. J. Roy. Statist. Soc. (B), 17 (1955), 185–94.Google Scholar
(21)Motzkin, T. S. The assignment problem. Proc. Symp. Appl. Math., Vol. 6., Numerical Analysis. (New York, 1956), 109–25.Google Scholar
(22)Oxford Atlas (Revised ed.) (Oxford, 1952).Google Scholar
(23)Tompkins, C. Permutation problems. Proc. Symp. Appl. Math., Vol. 6. Numerical Analysis (New York, 1956), 195–211.Google Scholar
(24)Verblunsky, S.On the shortest path through a number of points. Proc. Amer. Math. Soc. (2) 6 (1951), 904–13.CrossRefGoogle Scholar
(25)von Neumann, J.Functional operators, Vol. I. Annals of Math. Studies, 21 (Princeton, 1950).CrossRefGoogle Scholar