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

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