TY - GEN
T1 - Guillotine subdivisions approximate polygonal subdivisions
T2 - 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
AU - Mitchell, Joseph S.B.
PY - 1996/1/28
Y1 - 1996/1/28
N2 - 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, and the constant factor that we obtain is a substantial improvement over all previous bounds: We obtain a factor of 2 for the L1 metric, and a factor of 2√2 for the L2 (Euclidean) metric.
AB - 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, and the constant factor that we obtain is a substantial improvement over all previous bounds: We obtain a factor of 2 for the L1 metric, and a factor of 2√2 for the L2 (Euclidean) metric.
UR - https://www.scopus.com/pages/publications/0039331929
M3 - Conference contribution
AN - SCOPUS:0039331929
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 402
EP - 408
BT - Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
PB - Association for Computing Machinery
Y2 - 28 January 1996 through 30 January 1996
ER -