Pants decomposition of the punctured plane

S.H. Poon, S. Thite

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationAbstracts 22nd European Workshop on Computational Geometry (EWCG 2006, Delphi, Greece, March 27-29, 2006)
EditorsI. Emiris, M. Karavelas, L. Palios
Pages99-102
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Pants decomposition of the punctured plane'. Together they form a unique fingerprint.

Cite this