Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- 1 January 2005
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 35 (1), 91-109
- https://doi.org/10.1137/s0097539703435297
Abstract
We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in 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+epsilon using only (O) over tilde(root n poly(1/epsilon)) 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.Keywords
This publication has 13 references indexed in Scilit:
- Algorithms for dynamic geometric problems over data streamsPublished by Association for Computing Machinery (ACM) ,2004
- Fast Greedy Algorithms for Constructing Sparse Geometric SpannersSIAM Journal on Computing, 2002
- Dynamic algorithms for geometric spanners of small diameter: Randomized solutionsComputational Geometry, 1999
- Efficient construction of a bounded-degree spanner with low weightAlgorithmica, 1997
- Dynamic Euclidean minimum spanning trees and extrema of binary functionsDiscrete & Computational Geometry, 1995
- A proof of the Gilbert-Pollak conjecture on the Steiner ratioAlgorithmica, 1992
- Euclidean minimum spanning trees and bichromatic closest pairsDiscrete & Computational Geometry, 1991
- A Functional Approach to Data Structures and Its Use in Multidimensional SearchingSIAM Journal on Computing, 1988
- Filtering Search: A New Approach to Query-AnsweringSIAM Journal on Computing, 1986
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related ProblemsSIAM Journal on Computing, 1982