An approximation algorithm for cutting out convex polygons
type: Item
instance of: scholarly article
title: An approximation algorithm for cutting out convex polygons
zbMATH Open document ID: 1082.65020
author: Adrian Dumitrescu
published in: Computational Geometry
publication date: 2004-11-18T00:00:00Z
review text: Given a polygonal piece of a paper \(Q\) with a polygon \(P\) drawn in it, cut \(P\) out of the paper to minimize the total length of cut segments. An polynomial-time \(O(\log n)\)-approximation is presented for the above problem. The author conjectures that if \(P\) is enclosed in a minimum axis-aligned rectangle \(Q\), an optimal edge-cutting gives a constant-factor approximation algorithm for cutting \(P\) out of \(Q\).
reviewed by: Du Ding-Zhu
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 2116165
zbMATH Keywords: convex polygons
zbMATH Keywords: stock cutting
zbMATH Keywords: approximation algorithm
zbMATH Keywords: combinatorial geometry
zbMATH Keywords: complexity of cutting
zbMATH Keywords: optimal edge-cutting
MaRDI profile type: Publication
full work available at URL: j.comgeo.2004.01.010
OpenAlex ID: W2013409484
cites work: Stock cutting to minimize cutting length
cites work: Polygons cuttable by a circular saw
cites work: The cost of cutting out convex \(n\)-gons
cites work: Cutting glass
DOI: 10.1016/J.COMGEO.2004.01.010
description: scientific article; zbMATH DE number 2116165