Efficient search of a minimum tree on points in a space with the $l_1$-norm

Abstract

In this paper, we consider the minimum spanning tree problem (for short, MSTP) on an arbitrary set of $n$ points of $d$-dimensional space in $l_1$-norm. For this problem, for each fixed $d\ge 2$, there is a known algorithm of the computational complexity $O(n\cdot (\log n+{\log }^{r_d}n\cdot \log \log n)big)$, where $r_d\in \{0,1,2,4\}$ for $d\in \{2,3,4,5\}$ and $r_d=d$ for $d\ge 6$. For $d=3$, this result can be improved to the computational complexity $O(n\cdot \log n)$. In this paper, for any fixed $d\ge 2$, an algorithm with the computational complexity $O(n\cdot {\log }^{d-1}n)$ is proposed to solve the considered MSTP, which improves the previous achievement for $d\ge 6$.

8 pages, in Russian language, 0 figures