Geodesic
The Fermat-Steiner problem in the space of compact subsets of $\mathbb R^m$ endowed with the Hausdorff metric
Sbornik. Mathematics, Tome 212 (2021) no. 1, pp. 25-56 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The Fermat-Steiner problem consists in finding all points in a metric space $X$ at which the sum of the distances to fixed points $A_1,\dots,A_n$ of $X$ attains its minimum value. This problem is studied in the metric space $\mathscr{H}(\mathbb R^m)$ of all nonempty compact subsets of the Euclidean space $\mathbb R^m$, and the $A_i$ are pairwise disjoint finite sets in $\mathbb R^m$. The set of solutions of this problem (which are called Steiner compact sets) falls into different classes in accordance with the distances to the $A_i$. Each class contains an inclusion-greatest element and inclusion-minimal elements (a maximal Steiner compact set and minimal Steiner compact sets, respectively). We find a necessary and sufficient condition for a compact set to be a minimal Steiner compact set in a given class, provide an algorithm for constructing such compact sets and find a sharp estimate for their cardinalities. We also put forward a number of geometric properties of minimal and maximal compact sets. The results obtained can significantly facilitate the solution of specific problems, which is demonstrated by the well-known example of a symmetric set $\{A_1,A_2,A_3\}\subset\mathbb R^2$, for which all Steiner compact sets are asymmetric. The analysis of this case is significantly simplified due to the technique developed. Bibliography 16 titles.
Keywords: minimal networks, Fermat-Steiner problem, Steiner problem, metric geometry.
Mots-clés : Hausdorff distance 
@article{SM_2021_212_1_a1,
     author = {A. Kh. Galstyan and A. O. Ivanov and A. A. Tuzhilin},
     title = {The {Fermat-Steiner} problem in the space of compact subsets of~$\mathbb R^m$ endowed with the {Hausdorff} metric},
     journal = {Sbornik. Mathematics},
     pages = {25--56},
     year = {2021},
     volume = {212},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2021_212_1_a1/}
}
TY  - JOUR
AU  - A. Kh. Galstyan
AU  - A. O. Ivanov
AU  - A. A. Tuzhilin
TI  - The Fermat-Steiner problem in the space of compact subsets of $\mathbb R^m$ endowed with the Hausdorff metric
JO  - Sbornik. Mathematics
PY  - 2021
SP  - 25
EP  - 56
VL  - 212
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SM_2021_212_1_a1/
LA  - en
ID  - SM_2021_212_1_a1
ER  - 
%0 Journal Article
%A A. Kh. Galstyan
%A A. O. Ivanov
%A A. A. Tuzhilin
%T The Fermat-Steiner problem in the space of compact subsets of $\mathbb R^m$ endowed with the Hausdorff metric
%J Sbornik. Mathematics
%D 2021
%P 25-56
%V 212
%N 1
%U http://geodesic.mathdoc.fr/item/SM_2021_212_1_a1/
%G en
%F SM_2021_212_1_a1
A. Kh. Galstyan; A. O. Ivanov; A. A. Tuzhilin. The Fermat-Steiner problem in the space of compact subsets of $\mathbb R^m$ endowed with the Hausdorff metric. Sbornik. Mathematics, Tome 212 (2021) no. 1, pp. 25-56. http://geodesic.mathdoc.fr/item/SM_2021_212_1_a1/

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

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

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

[4] V. Jarník, M. Kössler, “O minimálních grafech, obsahujících $n$ daných bodů [On minimal graphs containing $n$ given points]”, Časopis Pěst. Mat. Fys., 63:8 (1934), 223–235 | DOI | Zbl

[5] R. Courant, H. Robbins, What is mathematics?, Oxford Univ. Press, New York, 1941, xix+521 pp. | MR | Zbl

[6] Z. Drezner, K. Klamroth, A. Schöbel, G. O. Wesolowsky, “The Weber problem”, Facility location: applications and theory, Springer, Berlin, 2002, 1–36 | MR | Zbl

[7] A. Ivanov, A. Tropin, A. Tuzhilin, “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] S. Schlicker, 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

[9] D. Burago, Yu. Burago, S. Ivanov, A course in metric geometry, Grad. Stud. Math., 33, Amer. Math. Soc., Providence, RI, 2001, xiv+415 pp. | DOI | MR | Zbl

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

[11] F. Mémoli, “On the use of Gromov–Hausdorff distances for shape comparison”, Eurographics symposium on point based graphics, The Eurographics Association, Prague, 2007, 81–90 | DOI

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

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

[14] O. Melnikov, R. Tyshkevich, V. Yemelichev, V. Sarvanov, Lectures on graph theory, Bibliographisches Institut, Mannheim, 1994, x+371 pp. | MR | Zbl | Zbl

[15] A. O. Ivanov, A. A. Tuzhilin, Geometriya rasstoyanii Khausdorfa i Gromova–Khausdorfa: sluchai kompaktov, Izd-vo Popechitelskogo soveta mekh.-matem. f-ta MGU, M., 2017, 111 pp.

[16] A. M. Tropin, Minimalnye derevya Shteinera v prostranstve s metrikoi Khausdorfa, Diplomnaya rabota, Mekh.-matem. f-t MGU, M., 2014