The problem of cutting a convex polygon out of a piece of paper Q with minimum total cutting length is a well studied problem in computational geometry. Researchers studied several variations of the problem, such as P and Q are convex or non-convex polygons and the cuts are line cuts or rays cuts. In this paper we consider yet another variation of the problem where Q is a circle and is convex polygon such that P is bounded by a half circle of Q and all the cuts are line cuts. We give a simple linear time O(log n)-approximation algorithm for this problem where is the number of vertices of P.
展开▼
