---
res:
bibo_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.\r\n\r\n\r\nRead
More: https://epubs.siam.org/doi/10.1137/S0097539703435297\r\n@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Artur
foaf_name: Czumaj, Artur
foaf_surname: Czumaj
- foaf_Person:
foaf_givenName: Funda
foaf_name: Ergün, Funda
foaf_surname: Ergün
- foaf_Person:
foaf_givenName: Lance
foaf_name: Fortnow, Lance
foaf_surname: Fortnow
- foaf_Person:
foaf_givenName: Avner
foaf_name: Magen, Avner
foaf_surname: Magen
- foaf_Person:
foaf_givenName: Ilan
foaf_name: Newman, Ilan
foaf_surname: Newman
- foaf_Person:
foaf_givenName: Ronitt
foaf_name: Rubinfeld, Ronitt
foaf_surname: Rubinfeld
- foaf_Person:
foaf_givenName: Christian
foaf_name: Sohler, Christian
foaf_surname: Sohler
bibo_doi: 10.1137/s0097539703435297
bibo_issue: '1'
bibo_volume: 35
dct_date: 2005^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0097-5397
- http://id.crossref.org/issn/1095-7111
dct_language: eng
dct_title: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear
Time@
...