A constant-factor approximation algorithm for the geometric k-MST problem in the plane

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₁ metric, and a factor of 2√2 (resp., 3.266) for the L₂ (Euclidean) metric in the case in which Steiner points are allowed (resp., not allowed).