Faster geometric k-point MST approximation.
D. Eppstein.
Tech. Rep. 95-13, ICS, UCI, 1995.
Comp. Geom. Theory & Applications 8: 231–240, 1997,
doi:10.1016/S0925-7721(96)00021-1.
Various authors have looked at a variant of geometric clustering in which one must select \(k\) points that can be connected by a small spanning tree. The problem is \(\mathsf{NP}\)-complete (for variable \(k\)); good approximations are known based on dynamic programming techniques but the time dependence on \(n\) is high. This paper describes a faster approximation algorithm based on dynamic programming in quadtrees, and a general technique based on that in "Iterated nearest neighbors" for reducing the dependence on \(n\) in any approximation algorithm.