Volume 5 Number 1 (Jan. 2010)
Home > Archive > 2010 > Volume 5 Number 1 (Jan. 2010) >
JCP 2010 Vol.5(1): 4-11 ISSN: 1796-203X
doi: 10.4304/jcp.5.1.4-11

Cutting a Cornered Convex Polygon Out of a Circle

Syed Ishtiaque Ahmed, Md. Ariful Islam, and Masud Hasan
Department of Computer Science and Engineering Bangladesh University of Engineering and Technology Dhaka 1000, Bangladesh

Abstract—The problem of cutting a convex polygon P out of a piece of planar material 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 ray cuts. In this paper we consider yet another variation of the problem where Q is a circle and P is a convex polygon such that P is bounded by a half circle of Q and all the cuts are line cuts. We give two algorithms for solving this problem. Our first algorithm is an O(log n)-approximation algorithm with O(n) running time, where n is the number of edges of P. The second algorithm is a constant factor approximation algorithm with approximation ratio 6.48 and running time O(n3).

Index Terms—algorithms, approximation algorithms, computational geometry, line cut, ray cut, polygon cutting, rotating calipers

[PDF]

Cite: Syed Ishtiaque Ahmed, Md. Ariful Islam, and Masud Hasan, " Cutting a Cornered Convex Polygon Out of a Circle," Journal of Computers vol. 5, no. 1, pp. 4-11, 2010.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>