A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees
Sunil Arya, David M. Mount · 2015
The Euclidean minimum spanning tree (EMST) is a fundamental and widely studied structure. In the approximate version we are given an n-element point set P in ℝd and an error parameter ∊ > 0, and the objective is to compute a spanning tree over P whose weight is at most (1 + ∊) times that of the true minimum spanning tree. Assuming that d is a fixed constant, existing algorithms have running times that (up to logarithmic factors) grow as O(n/∊Ω(d)). We present an algorithm whose running time is . Thus, this is the first algorithm for approximate EMSTs that eliminates the exponential ∊ dependence on dimension. (Note that the O-notation conceals a constant factor of the form O(1)d.) The algorithm is deterministic and very simple.