@article{18855,
  abstract     = {{We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries.


Read More: https://epubs.siam.org/doi/10.1137/S0097539703435297
}},
  author       = {{Czumaj, Artur and Ergün, Funda and Fortnow, Lance and Magen, Avner and Newman, Ilan and Rubinfeld, Ronitt and Sohler, Christian}},
  issn         = {{0097-5397}},
  journal      = {{SIAM Journal on Computing}},
  number       = {{1}},
  pages        = {{91--109}},
  title        = {{{Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time}}},
  doi          = {{10.1137/s0097539703435297}},
  volume       = {{35}},
  year         = {{2005}},
}