Computing a (1+epsilon)-approximate geometric minimum-diameter spanning tree Academic Article uri icon


  • 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. For several years, the best upper bound on the time to compute a GMDST was cubic with respect to the number of points in the input set. Recently, Timothy Chan introduced a sub-cubic time algorithm. In this paper, we present an 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).

publication date

  • January 1, 2004