Pants decomposition of the punctured plane

A pants decomposition of an orientable surface ?? is a collection of simple cycles that partition ?? into pants, i.e., surfaces of genus zero with three boundary cycles. Given a set P of n points in the plane E2, we consider the problem of computing a pants decomposition of ?? = E2 \ P of minimum total length. We give a polynomial-time approximation scheme using Mitchell’s guillotine rectilinear subdivisions. We give an O(n4)-time algorithm to compute the shortest pants decomposition of ?? when the cycles are restricted to be axis-aligned boxes, and an O(n2)-time algorithm when all the points lie on a line; both exact algorithms use dynamic programming with Yao’s speedup.