Efficient Search for a Minimum Tree in a Space with the l₁-Norm

The problem of finding a minimum spanning tree (MST) on an arbitrary set of n points in d -space with the l₁ -norm is considered. It is known that, for each fixed d≥ 2 , there exists an algorithm solving this problem in time O(n(log n+logrdnloglog n)) , where rd∈\0,1, 2,4\ if d∈ \2,3,4,5\ and rd=d if d≥ 6 . For $$d=3$$ , the complexity can be improved to O(nlog n) . In the paper, for any fixed d≥ 2 , an algorithm of complexity O(nlogᵈ⁻¹ n) solving the MST problem under consideration is proposed, which improves the existing algorithms for d≥ 6 .