A Constant-Factor Approximation Algorithm for the Geometric k -MST Problem in the Plane
Joseph S. B. Mitchell, Avrim L. Blum, Prasad Chalasani, Santosh Vempala · SIAM Journal on Computing · 1998
We show that any rectilinear polygonal subdivision in the plane can be converted into a "guillotine" subdivision whose length is at most twice that of the original subdivision. "Guillotine" subdivisions have a simple recursive structure that allows one to search for "optimal" such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a very simple proof that the k-MST problem in the plane has a constant-factor polynomial-time approximation algorithm: we obtain a factor of 2 (resp., 3) for the L 1 metric, and a factor of $2\sqrt{2}$ (resp., 3.266) for the L 2 (Euclidean) metric in the case in which Steiner points are allowed (resp., not allowed).