| Sublinear-Time Approximation of Euclidean Minimum Spanning Tree (2002) | |||||||||||||||||
Abstract | |||||||||||||||||
| We consider the problem of estimating the weight of a Euclidean minimum spanning tree for a set of n points in R . We focus on the situation when 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. Our main result is that if we assume the access to the input is supported by a minimal bounding cube of the input, by orthogonal range queries, and by cone approximate nearest neighbors queries, then it is possible to estimate the weight of a Euclidean minimum spanning tree of P to within 1 + " using only e O( n poly(1=")) queries for constant d. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||