Аннотация:
Проблема Ферма–Штейнера состоит в поиске всех точек метрического пространства $X$, в которых достигает минимума сумма расстояний до фиксированных точек $A_1,\dots,A_n$ из $X$. Эта задача изучается в метрическом пространстве $\mathscr{H}(\mathbb R^m)$ всех непустых компактных подмножеств евклидова пространства, где $A_i$ – его попарно не пересекающиеся конечные подмножества. Множество решений (так называемых компактов Штейнера) разбивается на классы, различающиеся наборами расстояний до точек $A_i$. В каждом классе существуют наибольший и минимальные по включению элементы (соответственно максимальный и минимальные компакты Штейнера). В работе получен критерий того, когда компакт является минимальным компактом Штейнера в заданном классе, приведен алгоритм построения таких компактов, получена точная оценка на число точек в них. Также доказан ряд геометрических свойств минимальных и максимальных компактов. Результаты данного исследования могут существенно облегчить решение конкретных задач, что продемонстрировано на известном примере симметричного множества $\{A_1,A_2,A_3\}\subset \mathbb R^2$, для которого все компакты Штейнера несимметричны. Разбор этого случая удалось значительно упростить благодаря развитой в работе технике.
Библиография: 16 названий.
Ключевые слова:минимальные сети, расстояние Хаусдорфа, проблема Ферма–Штейнера, проблема Штейнера, метрическая геометрия.