Back to Search
Start Over
An approximation algorithm for cutting out convex polygons
- Source :
-
Computational Geometry . Nov2004, Vol. 29 Issue 3, p223-231. 9p. - Publication Year :
- 2004
-
Abstract
- We provide an <f>O(logn)</f>-approximation algorithm for the following problem. Given a convex <f>n</f>-gon <f>P</f>, drawn on a convex piece of paper, cut <f>P</f> out of the piece of paper in the cheapest possible way. No polynomial-time approximation algorithm was known for this problem posed in 1985. [Copyright &y& Elsevier]
- Subjects :
- *ALGORITHMS
*POLYGONS
*POLYNOMIALS
*CONVEX bodies
Subjects
Details
- Language :
- English
- ISSN :
- 09257721
- Volume :
- 29
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 14512342
- Full Text :
- https://doi.org/10.1016/j.comgeo.2004.01.010