Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
Authors:
- Artur CzumajACArtur Czumaj
- Funda ErgünFEFunda Ergün
- Lance FortnowLFLance Fortnow
- Avner MagenAMAvner Magen
- Ilan NewmanINIlan Newman
- Ronitt RubinfeldRRRonitt Rubinfeld
- Christian SohlerCSChristian Sohler
- 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
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.
Keywords
This publication has 10 references indexed in Scilit:
- 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
- Computational Geometry1997
- 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