A PTAS for cutting out polygons with lines

DOI10.1007/s00453-008-9182-2zbMath1172.68062OpenAlexW2090581657MaRDI QIDQ1014794

Ovidiu Daescu, Sergey Bereg, Ming-Hui Jiang

Publication date: 29 April 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9182-2

zbMATH Keywords

approximation algorithmsstock cutting

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

CUTTING OUT POLYGONS WITH A CIRCULAR SAW, Approximation algorithms for cutting a convex polyhedron out of a sphere, Cutting a convex polyhedron out of a sphere, Approximation Algorithms for Cutting a Convex Polyhedron Out of a Sphere, Cutting out polygon collections with a saw

Cites Work

• Unnamed Item
• Stock cutting to minimize cutting length
• An approximation algorithm for cutting out convex polygons
• The cost of cutting out convex \(n\)-gons
• CUTTING OUT POLYGONS WITH LINES AND RAYS
• Computing and Combinatorics
• Polygons cuttable by a circular saw