Abstract
The problem of finding a minimum spanning tree (MST) on an arbitrary set of \(n\) points in \(d\) -space with the \(l_1\) -norm is considered. It is known that, for each fixed \(d\ge 2\) , there exists an algorithm solving this problem in time \(O(n(\log n+\log^{r_d}n\log\log n))\) , where \(r_d\in\{0,1, 2,4\}\) if \(d\in \{2,3,4,5\}\) and \(r_d=d\) if \(d\ge 6\) . For \(d=3\) , the complexity can be improved to \(O(n\log n)\) . In the paper, for any fixed \(d\geq 2\) , an algorithm of complexity \(O(n\log^{d-1} n)\) solving the MST problem under consideration is proposed, which improves the existing algorithms for \(d\geq 6\) .
