Моделирование оптимальных сетей в манхеттенском пространстве с помощью шарнирных механизмов

М. Ю. Житная

Московский государственный университет им. М. В. Ломоносова (г. Москва)

Аннотация: В широком смысле шарнирные механизмы представляют собой конструкции из жёстких элементов, соединённых таким образом, что некоторые их пары могут вращаться вокруг общей точки. Одной из основных задач, связанных с исследованием шарнирных механизмов, является описание возможных положений шарниров. Важными результатами в этой области являются теоремы Кинга [7], [8] и Кемпе [2]. Основным результатом настоящей статьи является конструктивное доказательство существования шарнирного механизма, который решает задачу оптимизации, а именно поиска кратчайшей сети для границы из $m \geqslant 1$ точек в пространстве размерности $n \geqslant 2$ с манхеттенской метрикой. Данная работа является продолжением предыдущих работ автора [3], [4], в которых были описаны механизмы, строящие кратчайшую сеть на евклидовой плоскости, а также минимальную параметрическую сеть в евклидовом пространстве размерности $k \geqslant 2$.

Ключевые слова: проблема Штейнера, шарнирный механизм, $\ell_1$-метрика.

УДК: 514.8+514.1

Поступила в редакцию: 29.12.2024
Принята в печать: 07.04.2025

DOI: 10.22405/2226-8383-2025-26-2-71-89