The cost of cutting out convex \(n\)-gons (Q1887073): Difference between revisions

The author discusses the following problem: Given a piece of paper \(Q\) with a polygon \(P\) drawn on it, cut \(P\) out of it in the cheapest possible way. A cut is a line \(l\) which divides the piece of paper into a number of pieces. The cost of a cut is the length of the intersection of the cutting line with the current piece of paper containing \(P\). The problem discussed asks for a cutting sequence whose total cost is minimum. Given a convex \(n\)-gon \(P\) on a piece of paper \(Q\) of unit diameter it is proved that it can be cut with a total cost of \(O(\log n)\). The bound is shown to be asymptotically tight.