Given a convex n-gon P drawn on a piece of paper Q of unit diameter we prove that it can be cut with a total cost of O(logn). This bound is shown to be asymptotically tight: a regular n-gon (whose circumscribed circle has radius, say, 1/3) drawn on a square piece of paper of unit diameter requires a cut cost of Omega(Iogn). (C) 2003 Published by Elsevier B.V.
展开▼
