Cutting a Convex Polygon Out of a Circle
Syed Ishtiaque Ahmed, Masud Hasan · 2009
Abstract — Efficient cutting strategy of a geometric shape, P out of another geometric shape, Q has been extensively studied in recent years. A number of variations of this problem has been addressed including P being convex or concave, cuts being line cut or ray cut, Q being a polygon or a circle etc. In this paper we give a simple linear time O (log n)-approximation algorithm for the problem where Q is a circle and n is the number of vertices of the convex polygon P. We also give a constant factor approximation algorithm for this problem which runs in O(n 3) time. Index Terms — Algorithm, circle, computational geometry, line cut, polygon cutting.