Utskrift från Malmö universitet - mau.se

# Minimum Spanning Trees in d Dimensions

 There are no files associated with this item..
Overview of item record
 Publication Article, peer reviewed scientific Title Minimum Spanning Trees in d Dimensions Author ; ; Date 1999 English abstract It is shown that a minimum spanning tree of $n$ points in $R^d$ under any fixed $L_p$-metric, with $p=1,2,\ldots,\infty$, can be computed in optimal $O(T_d(n,n) )$ time in the algebraic computational tree model. $T_d(n,m)$ denotes the time to find a bichromatic closest pair between $n$ red points and $m$ blue points. The previous bound in the model was $O( T_d(n,n) \log n )$ and it was proved only for the $L_2$ (Euclidean) metric. Furthermore, for $d = 3$ it is shown that a minimum spanning tree can be found in $O(n \log n)$ time under the $L_1$ and $L_\infty$-metrics. This is optimal in the algebraic computation tree model. The previous bound was $O(n \log n \log \log n)$. Publisher Publishing Association Nordic Journal of Computing Host/Issue Nordic Journal of Computing;4 Volume 6 Pages 16 Page 446-461 Language eng (iso) Subject AlgorithmsSciencesResearch Subject Categories::MATHEMATICS::Applied mathematics::Theoretical computer science Handle http://hdl.handle.net/2043/6642 Permalink to this page
 Tweet