---
_id: '18855'
abstract:
- lang: eng
  text: "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"
author:
- first_name: Artur
  full_name: Czumaj, Artur
  last_name: Czumaj
- first_name: Funda
  full_name: Ergün, Funda
  last_name: Ergün
- first_name: Lance
  full_name: Fortnow, Lance
  last_name: Fortnow
- first_name: Avner
  full_name: Magen, Avner
  last_name: Magen
- first_name: Ilan
  full_name: Newman, Ilan
  last_name: Newman
- first_name: Ronitt
  full_name: Rubinfeld, Ronitt
  last_name: Rubinfeld
- first_name: Christian
  full_name: Sohler, Christian
  last_name: Sohler
citation:
  ama: Czumaj A, Ergün F, Fortnow L, et al. Approximating the Weight of the Euclidean
    Minimum Spanning Tree in Sublinear Time. <i>SIAM Journal on Computing</i>. 2005;35(1):91-109.
    doi:<a href="https://doi.org/10.1137/s0097539703435297">10.1137/s0097539703435297</a>
  apa: Czumaj, A., Ergün, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., &#38;
    Sohler, C. (2005). Approximating the Weight of the Euclidean Minimum Spanning
    Tree in Sublinear Time. <i>SIAM Journal on Computing</i>, <i>35</i>(1), 91–109.
    <a href="https://doi.org/10.1137/s0097539703435297">https://doi.org/10.1137/s0097539703435297</a>
  bibtex: '@article{Czumaj_Ergün_Fortnow_Magen_Newman_Rubinfeld_Sohler_2005, title={Approximating
    the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time}, volume={35},
    DOI={<a href="https://doi.org/10.1137/s0097539703435297">10.1137/s0097539703435297</a>},
    number={1}, journal={SIAM Journal on Computing}, author={Czumaj, Artur and Ergün,
    Funda and Fortnow, Lance and Magen, Avner and Newman, Ilan and Rubinfeld, Ronitt
    and Sohler, Christian}, year={2005}, pages={91–109} }'
  chicago: 'Czumaj, Artur, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt
    Rubinfeld, and Christian Sohler. “Approximating the Weight of the Euclidean Minimum
    Spanning Tree in Sublinear Time.” <i>SIAM Journal on Computing</i> 35, no. 1 (2005):
    91–109. <a href="https://doi.org/10.1137/s0097539703435297">https://doi.org/10.1137/s0097539703435297</a>.'
  ieee: A. Czumaj <i>et al.</i>, “Approximating the Weight of the Euclidean Minimum
    Spanning Tree in Sublinear Time,” <i>SIAM Journal on Computing</i>, vol. 35, no.
    1, pp. 91–109, 2005.
  mla: Czumaj, Artur, et al. “Approximating the Weight of the Euclidean Minimum Spanning
    Tree in Sublinear Time.” <i>SIAM Journal on Computing</i>, vol. 35, no. 1, 2005,
    pp. 91–109, doi:<a href="https://doi.org/10.1137/s0097539703435297">10.1137/s0097539703435297</a>.
  short: A. Czumaj, F. Ergün, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, C. Sohler,
    SIAM Journal on Computing 35 (2005) 91–109.
date_created: 2020-09-02T12:13:26Z
date_updated: 2022-01-06T06:53:53Z
department:
- _id: '63'
doi: 10.1137/s0097539703435297
intvolume: '        35'
issue: '1'
language:
- iso: eng
page: 91-109
publication: SIAM Journal on Computing
publication_identifier:
  issn:
  - 0097-5397
  - 1095-7111
publication_status: published
status: public
title: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear
  Time
type: journal_article
user_id: '15415'
volume: 35
year: '2005'
...