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\geqslant 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\geqslant 6$. For $d=3$, the complexity can be improved to $O(n\log n)$. In the paper, for any fixed $d\geqslant 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\geqslant 6$.
Keywords:computational geometry, minimum spanning tree problem, efficient algorithm.
Fulltext:
PDF file (574 kB)
First page:
PDF file
