The Fermat-Steiner problem in the space of compact subsets of~$\mathbb R^m$ endowed with the Hausdorff metric

A. Kh. Galstyan ; A. O. Ivanov ; A. A. Tuzhilin

Sbornik. Mathematics, Tome 212 (2021) no. 1, pp. 25-56

Résumé

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.

Détail

Keywords: minimal networks, Fermat-Steiner problem, Steiner problem, metric geometry.
Mots-clés : Hausdorff distance