Approximating the Geometric Minimum-Diameter Spanning Tree
Michael J. Spriggs, Julian Keil, Sergei N. Bespamyatnikh, Michael Segal, Jack Scott Snoeyink · 2003
Given a set P of points in the plane, a geometric minimum-diameter spanning tree (GMDST) of P is a spanning tree of P such that the longest path through the tree is minimized. In this paper, we present an approximation algorithm that generates a tree whose diameter is no more than (1 + ɛ) times that of a GMDST, for any ɛ>0. Our algorithm reduces the problem to several grid-aligned versions of the problem and runs within time O(ɛ −3 + n) and space O(n) improving the result by Gudmundsson et al. [4]. 1