---
_id: '18791'
abstract:
- lang: eng
  text: We consider the problem of finding the weight of a Euclidean minimum spanning
    tree for a set of n points in ℝd. 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. 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 + ε using only \~{O}(√ poly(1/ε))
    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 neighbors queries.
author:
- first_name: Avner
  full_name: Magen, Avner
  last_name: Magen
- first_name: Funda
  full_name: Ergun, Funda
  last_name: Ergun
- first_name: Christian
  full_name: Sohler, Christian
  last_name: Sohler
- first_name: Ronitt
  full_name: Rubinfeld, Ronitt
  last_name: Rubinfeld
- first_name: Artur
  full_name: Czumaj, Artur
  last_name: Czumaj
- first_name: Ilan
  full_name: Newman, Ilan
  last_name: Newman
- first_name: Lance
  full_name: Fortnow, Lance
  last_name: Fortnow
citation:
  ama: 'Magen A, Ergun F, Sohler C, et al. Sublinear Approximation of Euclidean Minimum
    Spanning Tree. In: <i>Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms
    (SODA 2003)</i>. ; 2003:813–822.'
  apa: Magen, A., Ergun, F., Sohler, C., Rubinfeld, R., Czumaj, A., Newman, I., &#38;
    Fortnow, L. (2003). Sublinear Approximation of Euclidean Minimum Spanning Tree.
    In <i>Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA
    2003)</i> (pp. 813–822).
  bibtex: '@inproceedings{Magen_Ergun_Sohler_Rubinfeld_Czumaj_Newman_Fortnow_2003,
    title={Sublinear Approximation of Euclidean Minimum Spanning Tree}, booktitle={Proceedings
    of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)}, author={Magen,
    Avner and Ergun, Funda and Sohler, Christian and Rubinfeld, Ronitt and Czumaj,
    Artur and Newman, Ilan and Fortnow, Lance}, year={2003}, pages={813–822} }'
  chicago: Magen, Avner, Funda Ergun, Christian Sohler, Ronitt Rubinfeld, Artur Czumaj,
    Ilan Newman, and Lance Fortnow. “Sublinear Approximation of Euclidean Minimum
    Spanning Tree.” In <i>Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms
    (SODA 2003)</i>, 813–822, 2003.
  ieee: A. Magen <i>et al.</i>, “Sublinear Approximation of Euclidean Minimum Spanning
    Tree,” in <i>Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms
    (SODA 2003)</i>, 2003, pp. 813–822.
  mla: Magen, Avner, et al. “Sublinear Approximation of Euclidean Minimum Spanning
    Tree.” <i>Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA
    2003)</i>, 2003, pp. 813–822.
  short: 'A. Magen, F. Ergun, C. Sohler, R. Rubinfeld, A. Czumaj, I. Newman, L. Fortnow,
    in: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003),
    2003, pp. 813–822.'
date_created: 2020-09-01T14:15:33Z
date_updated: 2022-01-06T06:53:52Z
department:
- _id: '63'
language:
- iso: eng
page: 813–822
publication: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA
  2003)
publication_identifier:
  isbn:
  - '0898715385'
status: public
title: Sublinear Approximation of Euclidean Minimum Spanning Tree
type: conference
user_id: '15415'
year: '2003'
...