Faster geometric k-point MST approximation

We give fast new approximation algorithms for the problem of choosing k planar points out of n to minimize the length of their minimum spanning tree (equivalently, of their traveling salesman tour or Steiner tree). For any x less than or equal to k, we can find an approximation achieving approximation ratio O(log k/log x) in time O(n log n + 2(x)kn log k). In particular, we get an approximation with ratio O(log k/loglog n) in time O(kn(1+epsilon)). We also show how to speed up other approximation methods without worsening their approximation ratios; for instance we can achieve a 1 + epsilon approximation ratio in time O(n(log n + k(O(1/epsilon)))). (C) 1997 Elsevier Science B.V.