Boundary stability in the Fermat--Steiner problem in hyperspaces over finite-dimensional normed spaces

A. Kh. Galstyan

Čebyševskij sbornik, Tome 24 (2023) no. 2, pp. 81-128.

Résumé

The Fermat–Steiner problem is to find all points of the metric space $Y$ such that the sum of the distances from each of them to points from some fixed finite subset $A = \{A_1, \ldots, A_n\}$ of the space $Y$ is minimal. In this paper, this problem is considered in the case when $Y=\mathcal{H}(X)$ is the space of non-empty compact subsets of a finite-dimensional normed space $X$ endowed with the Hausdorff metric, i.e. $\mathcal{H}(X)$ is a hyperspace over $X$. The set $A$ is called boundary, all $A_i$ are called boundary sets, and the compact sets that realize the minimum of the sum of distances to $A_i$ 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 $A_i$ to a boundary consisting of their convex hulls $\mathrm{Conv}(A_i)$. By stability here we mean that the minimum of the sum of distances $S_A$ 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 $\mathcal{H}(X)$ were derived, two of which are based on the constructed theory of such sets. For the case of an unstable boundary $A = \{A_1, \ldots, A_n\}$, a method was developed to search for deformations of some element from $\mathcal{H}(X),$ which lead to compact sets that give a smaller value of the sum of distances to $\mathrm{Conv}(A_i)$ than $S_A.$ The theory constructed within the framework of this study was applied to one of the well-known from recent works boundary $A\subset \mathcal{H}(\mathbb{R}^2),$ namely, its instability was proved and compact sets were found realizing the sum of distances to $\mathrm{Conv}(A_i),$ less than $S_A.$

Détail

Keywords: metric geometry, hyperspaces, convex sets, Hausdorff distance, Steiner problem, Fermat–Steiner problem, extremal networks.

Bibliographie

[1] Ivanov A. O., Tuzhilin A. A., Branching solutions to one–dimensional variational problems, World Sci. Publ., River Edge, NJ, 2001, xxii+342 pp. | MR | Zbl

[2] Cieslik D., Steiner minimal trees, Nonconvex Optim. Appl., 23, Kluwer Acad. Publ., Dordrecht, 1998, xii+319 pp. | DOI | MR | Zbl

[3] Ivanov A. O., Tuzhilin A. A., “Minimal networks: a review”, Advances in dynamical systems and control, Stud. Syst. Decis. Control, 69, Springer, Cham, 2016, 43–80 | DOI | MR | Zbl

[4] Hwang F. K., Richards D. S., Winter P., The Steiner Tree Problem, North–Holland, 1992, 339 pp. | MR | Zbl

[5] Jarnik V., Kössler M., “On minimal graphs containing n given points”, Časopis P̌est. Mat. Fys., 63:8 (1934), 223–235 | DOI | Zbl

[6] Courant R., Robbins H., What is mathematics? An elementary approach to ideas and methods, 3-rd ed., cor. and ad., Izdatelstvo MCNMO, M., 2001, 568 pp.

[7] Ivanov A., Tropin A., Tuzhilin A., “Fermat–Steiner problem in the metric space of compact sets endowed with Hausdorff distance”, J. Geom., 108:2 (2017), 575–590 | DOI | MR | Zbl

[8] Nadler S. B., Hyperspaces of sets, Marcel Dekker Inc., New York–Basel, 1978, 707 pp. | MR | Zbl

[9] Blackburn C. C., Lund K., Schlicker S., Sigmon P., Zupan A., “An introduction to the geometry of $\mathcal{H}(\mathbb{R}^n)$”, GVSU REU 2007, Grand Valley State Univ., Allendale, MI, 2007

[10] Memoli F., “On the use of Gromov–Hausdorff distances for shape comparison”, Eurographics symposium on point based graphics, The Eurographics Association, Prague, 2007, 81–90

[11] Memoli F., “Some properties of Gromov–Hausdorff distances”, Discrete Comput. Geom., 48:2 (2012), 416–440 | DOI | MR | Zbl

[12] Ivanov A. O., Tuzhilin A. A., “Isometry group of Gromov–Hausdorff space”, Mat. Vesnik, 71:1–2 (2019), 123–154 | MR | Zbl

[13] Galstyan A. Kh., Ivanov A. O., Tuzhilin A. A., “The Fermat–Steiner problem in the space of compact subsets of $\mathbb{R}^m$ endowed with the Hausdorff metric”, Sb. Math., 212:1 (2021), 25–56 | DOI | MR | Zbl

[14] Tropin A. M., “An Estimation of the Length of a Minimal Parametric Network in Hyperspaces under the Deformation of the Boundary Set”, Intelligent systems. Theory and Applications, 25:2 (2021), 81–107 | MR

[15] Mendelson B., Introduction to topology, Dover Publications, 1990, 206 pp. | MR | Zbl

[16] Leonard I. E., Lewis J. E., Geometry of convex sets, Wiley, 2015, 336 pp. | MR

[17] Alimov A. R., Tsarkov I. G., “Connection and other geometric properties of suns and Chebyshev sets”, Fundamental and applied mathematics, 19:4 (2014), 21–91

[18] Schlicker S., “The geometry of the Hausdorff metric”, GVSU REU 2008, Grand Valley State Univ., Allendale, MI, 2008, 11 pp. http://faculty.gvsu.edu/schlicks/HMG2008.pdf

[19] Burago D., Burago Yu., Ivanov S., A course in metric geometry, Institute for Computer Research, M.–Izhevsk, 2004, 512 pp. | MR

[20] Ivanov A. O., Tuzhilin A. A., Geometry of Hausdorff and Gromov–Hausdorff distances: the case of compact sets, Faculty of mechanics and mathematics of MSU, M., 2017, 111 pp.

[21] Galstyan A. Kh., “About the continuity of one operation with convex compacts in finite-dimensional normed spaces”, Chebyshevskii sbornik, 23:5 (2022), 152–160 | DOI | MR | Zbl

[22] Drusvyatskiy D., Convex analysis and nonsmooth optimization, University Lecture, 2020 https://sites.math.washington.edu/d̃drusv/crs/Math_516_2020/bookwithindex.pdf

[23] Galstyan A. Kh., Boundary stability in the Fermat–Steiner problem in hyperspaces over finite-dimensional normed spaces, 2022, arXiv: 2212.01881 | MR | Zbl