We study Steiner’s problem in the Gromov–Hausdorff space, i.e., in the space of compact metric spaces (considered up to isometry) endowed with the Gromov–Hausdorff distance. Since this space is not boundedly compact, the problem of the existence of a shortest network connecting a finite point set in this space is open. We prove that each finite family of finite metric spaces can be connected by a shortest network. Moreover, it turns out that there exists a shortest tree all of whose vertices are finite metric spaces. A bound for the number of points in such metric spaces is derived. As an example, the case of three-point metric spaces is considered. We also prove that the Gromov–Hausdorff space does not realise minimal fillings, i.e., shortest trees in it need not be minimal fillings of their boundaries.
Keywords: Steiner’s problem, shortest network, Steiner’s minimal tree, minimal filling, Gromov–Hausdorff space, Gromov–Hausdorff distance.
The paper was received by the Editorial Office on June 23, 2017.
A.O.Ivanov. Dr. Phys.-Math. Sci., Prof., Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Moscow, 119991 Russia,
e-mail: aoiva@mech.math.msu.su
N.K.Nikolaeva. Mathematics Teacher, SOSh NOU “Orthodox Saint-Peter School”, Moscow, 109028, Tessinskiy per., 3 Russia,
e-mail: nadkostnik@mail.ru
A.A.Tuzhilin. Dr. Phys.-Math. Sci., Prof., Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Moscow, 119991 Russia,
e-mail: tuz@mech.math.msu.su
REFERENCES
1. Memoli F. On the use of Gromov–Hausdorff distances for shape comparison. In: Proc. Eurographics Symposium on Point Based Graphics 2007, ed. by M. Botsch, R. Pajarola, B. Chen, and M. Zwicker, Prague, 2007, pp. 81–90, doi: 10.2312/SPBG/SPBG07/081-090 .
2. Hausdorff F. GrundzЈuge der Mengenlehre. Leipzig, Veit, 1914 [reprinted by AMS Chelsea in 1949], 476 p. ISBN: 978-0-8284-0061-9 .
3. Edwards D. The structure of superspace. Studies in Topology, ed. by N.M. Stavrakas, K.R. Allen, Proc. Conf., Univ. North Carolina, Charlotte, N. C., 1974; dedicated to Math. Sect. Polish Acad. Sci., N. Y.; London; San Francisco: Acad. Press, Inc., 1975, pp. 121–133. doi: 10.1016/B978-0-12-663450-1.50017-7 .
4. Gromov M. Groups of polynomial growth and expanding maps. In: Publications Mathematiques I.H.E.S., 1981, vol. 53, no. 1, pp. 53–78. doi: 10.1007/BF02698687 .
5. Burago D.Yu., Burago Yu.D., Ivanov S.V. A course in metric geometry, Ser. Graduate Studies in Mathematics, vol. 33, Providence: AMS, 2001, 415 p. ISBN: 0821821296 . Translated to Russian under the title Kurs metricheskoi geometrii. Moscow, Izhevsk: Inst. Komp’yut. Issled. Publ., 2004, 512 p.
6. Ivanov A.O., Nikolaeva N.K., Tuzhilin A.A. The Gromov–Hausdorff metric on the space of compact metric spaces is strictly intrinsic. Math. Notes, 2016, vol. 100, no. 6, pp. 171–173.
doi: 10.1134/S0001434616110298 .
7. Ivanov A.O., Tuzhilin A.A. Teoriya ekstremal’nykh setei [Extreme Networks Theory]. Moscow, Izhevsk: IInst. Komp’yut. Issled. Publ., 2003, 424 p. ISBN: 5-93972-292-X .
8. Garkavi A.L., Shmatkov V.A. On the Lame point and its generalizations in a normed space. Math. USSR-Sb., 1974, vol. 24, no. 2, pp. 267–286. doi: 10.1070/SM1974v024n02ABEH002187 .
9. Borodin P.A. An example of nonexistence of a Steiner point in a Banach space. Math. Notes, 2010, vol. 87, no. 3, pp. 485–488. doi: 10.1134/S0001434610030260 .
10. Bednov B.B., Strelkova N.P. On the existence of shortest networks in Banach spaces. Math. Notes, 2013, vol. 94, no. 1, pp. 41–48. doi: 10.1134/S0001434613070043 .
11. Ivanov A., Nikolaeva N., Tuzhilin A. Steiner problem in Gromov–Hausdorff space: the Case of finite metric spaces [e-resource]. 2016. 5 p. Available at: https://arxiv.org/pdf/1604.02170.pdf .
12. Ivanov A. O., Tuzhilin A. A. Minimal networks: A review. In: Advances in Dynamical Systems and Control. ed. by V.A. Sadovnochiy, M.Z. Zgurovsky. Cham: Springer Switzerland, 2016, Ser. Studies in Systems, Decision and Control, vol. 69, pp. 43–80. doi: 10.1007/978-3-319-40673-2_4 .
13. Ivanov A., Iliadis S., Tuzhilin A. Realizations of Gromov–Hausdorff distance [e-resource]. 2016. 6 p. Available at: https://arxiv.org/pdf/1603.08850.pdf .
14. Chowdhury S., Memoli F. Constructing geodesics on the space of compact metric spaces. 2016. 5 p. Available at: https://arxiv.org/pdf/1603.02385.pdf .
15. Ivanov A.O., Tuzhilin A.A. One-dimensional Gromov minimal filling problem. Sb. Math., 2012, vol. 203, no. 5, pp. 677–726. doi: 10.1070/SM2012v203n05ABEH004239 .
16. Bednov B.B., Borodin P.A. Banach spaces that realize minimal fillings. Sb. Math., 2014, vol. 205, no. 4, pp. 459–475. doi: 10.1070/SM2014v205n04ABEH004383 .
17. A.O. Ivanov, A.A. Tuzhilin, A.Y. Yeremin, E.S. Erokhovets, A.S. Pakhomova, O.V. Rubleva, N.P. Strelkova, E.I. Filonenko. Minimal’nye zapolneniya psevdometricheskikh prostranstv [Minimum fillings of pseudometric spaces]. Tr. seminara po vektornomu i tenzornomu analizu s ikh prilozheniyami k geometrii, mekhanike i fizike [Proc. Seminar on Vector and Tensor Analysis with their Applications to Geometry, Mechanics and Physics]. 2011, vol. 27, pp. 83–105. ISBN: 978-5-211-06253-5.
18. Ivanov A., Tuzhilin A. Gromov — Hausdorff distance, irreducible correspondences, Steiner problem, and minimal fillings. 2016. 11 p. Available at: https://arxiv.org/pdf/1604.06116.pdf .
