Pants Decomposition of the Punctured Plane

Details Pants Decomposition of the Punctured Plane Pants Decomposition of the Punctured Plane

2006-02-22

arxiv.org/abs/cs/0602080v1

Computer Science

Computational Geometry

5 pages, 1 grayscale figure

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Pants Decomposition of the Punctured Plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pants Decomposition of the Punctured Plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pants Decomposition of the Punctured Plane will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-88910