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.
|Title of host publication||Abstracts 22nd European Workshop on Computational Geometry (EWCG 2006, Delphi, Greece, March 27-29, 2006)|
|Editors||I. Emiris, M. Karavelas, L. Palios|
|Publication status||Published - 2006|