ALCOMFT-TR-03-92

Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld and Christian Sohler
Sublinear-Time Approximation of Euclidean Minimum Spanning Tree
Paderborn. Work packages 1 and 4. November 2003.

Abstract: We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in \REAL^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 + \eps using only \widetilde\O(\sqrt{n} \textpoly (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 neighbors queries.

Postscript file: ALCOMFT-TR-03-92.ps.gz (93 kb).