×

On the history of the Euclidean Steiner tree problem. (English) Zbl 1295.05002

Summary: The history of the Euclidean Steiner tree problem, which is the problem of constructing a shortest possible network interconnecting a set of given points in the Euclidean plane, goes back to Gergonne in the early nineteenth century. We present a detailed account of the mathematical contributions of some of the earliest papers on the Euclidean Steiner tree problem. Furthermore, we link these initial contributions with results from the recent literature on the problem.

MSC:

05-03 History of combinatorics
05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C12 Distance in graphs

Software:

GeoSteiner
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Arora, S. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM 45(5): 753–782. · Zbl 1064.90566 · doi:10.1145/290179.290180
[2] Beardwoord, J., J.H. Halton, and J.M. Hammersley. 1959. The shortest path through many points. Proceedings of Cambridge Philosophical Society 55: 299–327. · Zbl 0118.35601 · doi:10.1017/S0305004100034095
[3] Bopp, K. 1879. Üeber das kürzeste Verbindungssystem zwischen vier Punkten. PhD thesis, Universität Göttingen.
[4] Cavalieri, B. 1647. Exercitationes Geometricae Sex. · Zbl 0933.01004
[5] Cavalli-Sforza, L.L., and A.W.F. Edwards. 1967. Phylogenetic analysis: Models and estimation procedures. Evolution 21: 550–570. · doi:10.2307/2406616
[6] Cheng, X., Y. Li, D.Z. Du, and H.Q. Ngo. 2004. Steiner trees in industry. In Handbook of combinatorial optimization, vol. 5, ed. D.Z. Du, and P.M. Pardalos, 193–216. Dordrecht: Kluwer. · Zbl 1179.90277
[7] Choquet, G. 1938. Étude de certains réseaux de routes. Comptes Rendus Acad Sci 206: 310–313. · Zbl 0018.17603
[8] Cieslik, D. 2004a. The essential of Steiner’s problem in normed planes. Technical report 8, Ernst-Moritz-Arndt-Universität Greifswald, Preprint-Reihe Mathematik. · Zbl 1176.05021
[9] Cieslik, D. 2004b. Shortest connectivity–Introduction with applications in phylogeny, combinatorial optimization, vol. 17. New York: Springer.
[10] Cockayne, E.J. 1967. On the Steiner problem. Canadian Mathematical Bulletin 10: 431–450. · Zbl 0161.19203 · doi:10.4153/CMB-1967-041-8
[11] Colbourn, C.J., and C. Huybrechts. 2008. Fully gated graphs: Recognition and convex operations. Discrete Mathematics 308: 5184–5195. · Zbl 1193.05070 · doi:10.1016/j.disc.2007.09.039
[12] Courant, R. 1940. Soap film experiments with minimal surfaces. The American Mathematical Monthly 47: 167–174. · Zbl 0024.41704
[13] Courant, R., and H. Robbins. 1941. What is mathematics?. London: Oxford University Press. · JFM 67.0001.05
[14] Dahan-Dalmedico, A. 1986. Un texte de philosophie mathématique de Gergonne. Revue d’histoire des sciences 39: 97–126. · Zbl 0609.01017 · doi:10.3406/rhs.1986.4026
[15] de Fermat, P. 1891. Oeuvres, vol. 1. · JFM 23.0013.02
[16] Descartes, R. 1896. Oeuvres de Descartes, vol. II. Paris: J. Vrin.
[17] Du, D.Z., and W. Wu. 2007. Approximations for Steiner minimum trees. In Handbook of approximation algorithms and metaheuristics. Chapman and Hall/CRC.
[18] Du, D.Z., F.K. Hwang, G.D. Song, and G.Y. Ting. 1987a. Steiner minimal trees on sets of four points. Discrete and Computational Geometry 2: 401–414. · Zbl 0623.05013 · doi:10.1007/BF02187892
[19] Du, D.Z., F.K. Hwang, and J.F. Weng. 1987b. Steiner minimal trees for regular polygons. Discrete Computational Geometry 2: 65–84. · Zbl 0607.05022 · doi:10.1007/BF02187871
[20] Franksen, O.I., and I. Grattan-Guiness. 1989. The earliest contribution to location theory? Spatio-economic equilibrium with Lamé and Clapeyron, 1829. Mathematics and Computers in Simulation 31: 195–220. · Zbl 0672.01021 · doi:10.1016/0378-4754(89)90159-6
[21] Gander, M.J., K. Santugini, and A. Steiner. 2008. Shortest road network connecting cities. Bollettino dei docenti di matematica 56: 9–19.
[22] Garey, M.R., R.L. Graham, and D.S. Johnson. 1977. The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics 32(4): 835–859. · Zbl 0399.05023 · doi:10.1137/0132072
[23] Gergonne, J.D. 1810. Solutions purement géométriques des problèmes de minimis proposés aux pages 196, 232 et 292 de ce volume, et de divers autres problèmes analogues. Annales de Mathématiques pures et appliquées 1: 375–384.
[24] Gilbert, E.N. 1967. Minimum cost communication networks. Bell System Technical Journal 46: 2209–2227. · doi:10.1002/j.1538-7305.1967.tb04250.x
[25] Gilbert, E.N., and H.O. Pollak. 1968. Steiner minimal trees. SIAM Journal on Applied Mathematics 16(1): 1–29. · Zbl 0159.22001 · doi:10.1137/0116001
[26] Guggenbuhl, L. 1959. Gergonne, founder of the Annales de Mathmatiques. The Mathematics Teacher 52(8): 621–629.
[27] Hammersley, J.M. 1961. On Steiner’s network problem. Mathematika 8: 131–132. · Zbl 0108.35301 · doi:10.1112/S0025579300002242
[28] Hanan, M. 1966. On Steiner’s problem with rectilinear distance. SIAM Journal on Applied Mathematics 14(2): 255–265. · Zbl 0151.33205 · doi:10.1137/0114025
[29] Heinen, F. 1834. Über Systeme von Kräften. G. D. Bädeker.
[30] Hoffmann, E. 1890. Über das kürzeste Verbindungssystem zwischen vier Punkten der Ebene. In Program des Königlichen Gymnasiums zu Wetzlar für das Schuljahr von Ostern 1889 bis Ostern 1890. Schnitzler. · JFM 22.0287.01
[31] Jarník, V., and M. Kössler. 1934. O minimálních grafeth obeahujících n daných bodú. Cas Pest Mat a Fys 63: 223–235.
[32] Korte, B., and J. Nesetril. 2001. Vojtech Jarnik’s work in combinatorial optimization. Discrete Mathematics 235: 1–17. · doi:10.1016/S0012-365X(00)00256-9
[33] Krarup, J., and S. Vajda. 1997. On Torricelli’s geometrical solution to a problem of Fermat. IMA Journal of Management Mathematics 8(3): 215–224. doi: 10.1093/imaman/8.3.215 . · Zbl 0901.51010 · doi:10.1093/imaman/8.3.215
[34] Kupitz, Y.S., and H. Martini. 1997. Geometric aspects of the generalized Fermat–Torricelli problem. In Bolyai Society Mathematical Studies, vol. 6, ed. I. Barany, and K. Boroczky, 55–127. Budapest: Intuitive Geometry, Janos Bolyai Mathematical Society. · Zbl 0911.51021
[35] Lamé, G., and B. Clapeyron. 1829. Mémoire sur lapplication de la statique à la solution des problèmes relatifs à la théorie des moindres distances. Journal des Voies et Communications 10: 26–49.
[36] Melzak, Z.A. 1961. On the problem of Steiner. Canad Math Bull 4(2): 143–148. · Zbl 0101.13201 · doi:10.4153/CMB-1961-016-2
[37] Menger, K. 1931. Some applications of point-set methods. Annals of Mathematics, Second Series 32: 739–760. · Zbl 0003.02201 · doi:10.2307/1968317
[38] Miehle, W. 1958. Link-length minimization in networks. Operations Research 6(2): 232–243. · doi:10.1287/opre.6.2.232
[39] Ollerenshaw, D.K. 1978. Minimum networks linking four points in a plane. Bulletin of the Institute of Mathematics and its Applications 15: 208–211.
[40] Pollak, H. 1978. Some remarks on the Steiner problem. Journal of Combinatorial Theory, Series A 24(3): 278–295. · Zbl 0392.05021 · doi:10.1016/0097-3165(78)90058-4
[41] Rubinstein, J.H., D.A. Thomas, and N.C. Wormald. 1997. Steiner trees for terminals constrained to curves. SIAM Journal on Discrete Mathematics 10(1): 1–17. · Zbl 0869.05023 · doi:10.1137/S0895480192241190
[42] Schreiber, P. 1986. Zur Geschichte des sogenannten Steiner-Weber-Problems. Technical report, Wissenschaftliche Zeitschrift der Ernst-Moritz-Arndt-Universität Greifswald, Mathematisch-Naturwissenschaftliche Reihe. 58. · Zbl 0616.51001
[43] Schumacher, H.C. 1810. Géométrie analitique. Solution analitique d’un problème de géométrie. Annales de Mathématiques pures et appliquées 1: 193–195.
[44] Scriba, C.J., and P. Schreiber. 2010. 5000 Jahre Geometrie. Berlin: Springer. · Zbl 1177.01004
[45] Simpson, T. 1750. The Doctrine and applications of fluxions. London: John Nourse Publisher.
[46] Steiner, J. 1882. Gesammelte Werke, vol. II. Berlin: Reimer.
[47] Stigler, S.M. 1976. The anonymous Professor Gergonne. Historia Mathematica 3(1): 71–74. · Zbl 0334.01022 · doi:10.1016/0315-0860(76)90009-4
[48] Tédenat, M. 1810. Questions résolues. Solution du premier des deux problèmes proposés à la page 196 de ce volume. Annales de Mathématiques pures et appliquées 1: 285–291.
[49] Torricelli, E. 1919. De maximis et minimis. In Opere di Evangelista Torricelli, ed. G. Loria, and G. Vassura. Faenza, Italy.
[50] Viviani, V. 1659. De maximis et minimis geometrica divination in quintum Conicorum Apollonii Pergaei, Vol. II. Florence, Italy.
[51] Warme, D.M. 1998. Spanning Trees in Hypergraphs with Applications to Steiner Trees. PhD thesis, Computer Science Department, The University of Virginia · Zbl 0903.90175
[52] Warme, D.M., P. Winter, and M. Zachariasen. 1999. Exact solutions to large-scale plane Steiner tree problems. In Proceedings of the tenth annual ACM-SIAM symposium on discrete algorithms, 979–980. · Zbl 0929.68094
[53] Warme, D.M., P. Winter, and M. Zachariasen. 2001. GeoSteiner 3.1. Department of Computer Science, University of Copenhagen (DIKU), http://www.diku.dk/geosteiner/ .
[54] Winter, P., and M. Zachariasen. 1997. Euclidean Steiner minimum trees: an improved exact algorithm. Networks 30: 149–166. · Zbl 0893.90170 · doi:10.1002/(SICI)1097-0037(199710)30:3<149::AID-NET1>3.0.CO;2-L
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.