Nordic Journal of Computing Bibliography

Drago Krznaric, Christos Levcopoulos, and Bengt J. Nilsson. Minimum Spanning Trees in d Dimensions. Nordic Journal of Computing, 6(4):446-461, Winter 1999.
Abstract

It is shown that a minimum spanning tree of n points in R^d under any fixed Lp-metric, with p=1,2,...,infinity can be computed in optimal O( Td(n,n) ) time in the algebraic computational tree model. Td(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( Td(n,n) log n ) and it was proved only for the L2 (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 L1 and Linfinity-metrics. This is optimal in the algebraic computation tree model. The previous bound was O(n log n log log n).

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: algorithms, computational geometry, networks, trees

Selected references


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database