Эффективный поиск минимального дерева на точках пространства в $l_1$-норме

Математические заметки. 2025. Т. 117. № 5. С. 672–679.

Каймаков К. В., Малышев Д. С.

В данной работе рассматривается задача о минимальном остовном дереве (кратко, ЗМОД) на произвольном множестве $n$ точек $d$-мерного пространства в $l_1$-норме. Для этой задачи при каждом фиксированном $d\geq 2$ известен алгоритм сложности $O\big(n\cdot (\log\,n + \log^{r_d}\,n\cdot \log\log\,n)\big)$, где $r_d\in \{0,1,2,4\}$ при $d\in \{2,3,4,5\}$ и $r_d=d$ при $d\geq 6$. Для $d=3$ известно улучшение этого результата до сложности $O(n\cdot \log\,n)$. В настоящей работе при любом фиксированном $d\geq 2$ для решения рассматриваемой ЗМОД предлагается алгоритм со сложностью $O(n\cdot \log^{d-1}\,n)$, что улучшает предыдущее достижение при $d\geq 6$

Ключевые слова: эффективный алгоритм, efficient algorithm, computational geometry, вычислительная геометрия, задача о минимальном остовном дереве, minimum spanning tree problem