Boundary stability in the Fermat–Steiner problem in hyperspaces over finite-dimensional normed spaces
https://doi.org/10.22405/2226-8383-2023-24-2-81-128
Abstract
The Fermat–Steiner problem is to find all points of the metric space 𝑌 such that the sum of the distances from each of them to points from some fixed finite subset 𝐴 = {𝐴1, . . . ,𝐴𝑛} of the space 𝑌 is minimal. In this paper, this problem is considered in the case when 𝑌 = ℋ(𝑋) is
the space of non-empty compact subsets of a finite-dimensional normed space 𝑋 endowed with the Hausdorff metric, i.e. ℋ(𝑋) is a hyperspace over 𝑋. The set 𝐴 is called boundary, all 𝐴𝑖 are called boundary sets, and the compact sets that realize the minimum of the sum of distances to 𝐴𝑖 are called Steiner compacts.
In this paper, we study the question of stability in the Fermat–Steiner problem when passing from a boundary consisting of finite compact sets 𝐴𝑖 to a boundary consisting of their convex hulls Conv(𝐴𝑖). By stability here we mean that the minimum of the sum of distances 𝑆𝐴 does not change when passing to convex hulls of boundary compact sets.
The paper continued the study of geometric objects, namely, hook sets that arise in the Fermat–Steiner problem. Also three different sufficient conditions for the instability of the boundary from ℋ(𝑋) were derived, two of which are based on the constructed theory of such
sets. For the case of an unstable boundary 𝐴 = {𝐴1, . . . ,𝐴𝑛}, a method was developed to search for deformations of some element from ℋ(𝑋), which lead to compact sets that give a smaller value of the sum of distances to Conv(𝐴𝑖) than 𝑆𝐴.
The theory constructed within the framework of this study was applied to one of the wellknown from recent works boundary 𝐴 ⊂ ℋ(R2), namely, its instability was proved and compact sets were found realizing the sum of distances to Conv(𝐴𝑖), less than 𝑆𝐴.
About the Author
Arsen Khachaturovich Galstyan
Lomonosov Moscow State University
Russian Federation
Russian Federation
postgraduate student
References
1. Ivanov, A. O. & Tuzhilin, A. A. 2001, Branching solutions to one–dimensional variational problems, World Sci. Publ., River Edge, NJ, xxii+342 pp.
2. Cieslik, D. 1998, Steiner minimal trees, Nonconvex Optim. Appl., 23, Kluwer Acad. Publ., Dordrecht, xii+319 pp.
3. Ivanov, A. O. & Tuzhilin, A. A. 2016, “Minimal networks: a review”, Advances in dynamical systems and control, Stud. Syst. Decis. Control, 69, Springer, Cham, 43–80 pp.
4. Hwang, F. K., Richards, D. S. & Winter, P. 1992, The Steiner Tree Problem, North–Holland, 339 p.
5. Jarnik, V. & K¨ossler, M. 1934, “On minimal graphs containing n given points”, ˇ Casopis ˇ Pest. Mat. Fys., vol. 63, no. 8 , pp. 223–235.
6. Courant, R. & Robbins, H. 2001, What is mathematics? An elementary approach to ideas and methods, 3-rd ed., cor. and ad., Izdatelstvo MCNMO, М., p. 568.
7. Ivanov, A., Tropin, A. & Tuzhilin, A. 2017, “Fermat–Steiner problem in the metric space of compact sets endowed with Hausdorff distance”, J. Geom., vol. 108, no. 2, pp. 575–590.
8. Nadler, S. B. 1978, Hyperspaces of sets, Marcel Dekker Inc., New York and Basel, 707 p.
9. Blackburn, C. C., Lund, K., Schlicker, S., Sigmon, P. & Zupan, A. 2007, An introduction to the geometry of ℋ(R𝑛), GVSU REU 2007, Grand Valley State Univ., Allendale, MI.
10. Memoli, F. 2007, “On the use of Gromov–Hausdorff distances for shape comparison”, Eurographics symposium on point based graphics, The Eurographics Association, Prague, pp. 81–90.
11. Memoli, F. 2012, “Some properties of Gromov–Hausdorff distances”, Discrete Comput. Geom., vol. 48, no. 2, pp. 416–440.
12. Ivanov, A. O. & Tuzhilin, A. A. 2019, “Isometry group of Gromov–Hausdorff space”, Mat. Vesnik, vol. 71, no. 1–2, pp. 123–154.
13. Galstyan, A. Kh., Ivanov, A. O. & Tuzhilin, A. A. 2021, “The Fermat–Steiner problem in the space of compact subsets of R𝑚 endowed with the Hausdorff metric”, Sb. Math., vol. 212, no. 1, pp. 25–56.
14. Tropin, A. М. 2021, “An Estimation of the Length of a Minimal Parametric Network in Hyperspaces under the Deformation of the Boundary Set”, Intelligent systems. Theory and Applications, vol. 25, no. 2, pp. 81–107.
15. Mendelson, B. 1990, Introduction to topology, Dover Publications, 206 p.
16. Leonard, I. E. & Lewis, J. E. 2015, Geometry of convex sets, Wiley, 336 p.
17. Alimov, A. R. & Tsarkov, I. G. 2014, “Connection and other geometric properties of suns and Chebyshev sets”, Fundamental and applied mathematics, vol. 19, no. 4, pp. 21–91.
18. Schlicker, S. 2008,“The geometry of the Hausdorff metric”, GVSU REU 2008, Grand Valley State Univ., Allendale, MI, 11 pp., http://faculty.gvsu.edu/schlicks/ HMG2008.pdf.
19. Burago, D., Burago, Yu. & Ivanov, S. 2004, A course in metric geometry, Institute for Computer Research, Moscow–Izhevsk, p. 512.
20. Ivanov, A. O. & Tuzhilin, A. A. 2017, Geometry of Hausdorff and Gromov–Hausdorff distances: the case of compact sets, Faculty of mechanics and mathematics of MSU, Moscow, p. 111.
21. Galstyan, A. Kh. 2022, “About the continuity of one operation with convex compacts in finitedimensional normed spaces”, Chebyshevskii sbornik, vol. 23, no. 5, pp. 152–160.
22. Drusvyatskiy, D. 2020, Convex analysis and nonsmooth optimization, University Lecture, https://sites.math.washington.edu/ ddrusv/crs/Math_516_2020/bookwithindex.pdf
23. Galstyan A. Kh. 2022, “Boundary stability in the Fermat–Steiner problem in hyperspaces over finite-dimensional normed spaces” // arXiv:2212.01881
Review
For citations:
Galstyan A.Kh. Boundary stability in the Fermat–Steiner problem in hyperspaces over finite-dimensional normed spaces. Chebyshevskii Sbornik. 2023;24(2):81-128. (In Russ.) https://doi.org/10.22405/2226-8383-2023-24-2-81-128
Views:
208
Email this article 