An approximation algorithm for cutting out convex polygons

ABSTRACT

We provide an O(log n)-approximation algorithm for the following problem. Given a convex n-gon P, drawn on a convex piece of paper, cut P out of the piece of paper in the cheapest possible way. No approximation algorithm was known for this problem posed in 1985.

REFERENCES

• 1: Erik D. Demaine , Martin L. Demaine , Craig S. Kaplan, Polygons cuttable by a circular saw, Computational Geometry: Theory and Applications, v.20 n.1-2, p.69-84, October 2001 [doi>10.1016/S0925-7721(01)00036-0]
• 2: A. Dumitrescu, The cost of cutting out convex n-gons, manuscript (submitted), April 2002.
• 3: Jeff Erickson , Leonidas J. Guibas , Jorge Stolfi , Li Zhang, Separation-sensitive collision detection for convex objects, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.327-336, January 17-19, 1999, Baltimore, Maryland, United States
• 4: Mark H. Overmars , Emo Welzl, The complexity of cutting paper (extended abstract), Proceedings of the first annual symposium on Computational geometry, p.316-321, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323274]
• 5: J. Pach and G. Tardos, Cutting glass, Discrete & Computational Geometry, 24 (2000), 481--495.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Theory