An approximation algorithm for cutting out convex polygons (Q1886238)

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\).