Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time

Authors:
  • ACArtur Czumaj
    Artur Czumaj
  • FEFunda Ergün
    Funda Ergün
  • LFLance Fortnow
    Lance Fortnow
  • AMAvner Magen
    Avner Magen
  • INIlan Newman
    Ilan Newman
  • RRRonitt Rubinfeld
    Ronitt Rubinfeld
  • CSChristian Sohler
    Christian Sohler

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.

This publication has 10 references indexed in Scilit: