Cutting a cornered convex polygon out of a circle

Syed Ishtiaque Ahmed; Md Ariful Islam; Masud Hasan

doi:10.1109/ICCITECHN.2008.4802988

Cutting a cornered convex polygon out of a circle

Syed Ishtiaque Ahmed, Md Ariful Islam, Masud Hasan

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The problem of cutting a convex polygon P 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 P 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 n is the number of vertices of P.

Original language	English
Title of host publication	Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008
Pages	1-6
Number of pages	6
DOIs	https://doi.org/10.1109/ICCITECHN.2008.4802988
State	Published - 2008
Event	11th International Conference on Computer and Information Technology, ICCIT 2008 - Khulna, Bangladesh Duration: Dec 25 2008 → Dec 27 2008

Publication series

Name	Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008

Conference

Conference	11th International Conference on Computer and Information Technology, ICCIT 2008
Country/Territory	Bangladesh
City	Khulna
Period	12/25/08 → 12/27/08

Keywords

Algorithm
Circle
Computational geometry
Line cut
Polygon cutting

Access to Document

10.1109/ICCITECHN.2008.4802988

Cite this

Ahmed, S. I., Islam, M. A., & Hasan, M. (2008). Cutting a cornered convex polygon out of a circle. In Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008 (pp. 1-6). Article 4802988 (Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008). https://doi.org/10.1109/ICCITECHN.2008.4802988

@inproceedings{3f6bb0b6d88a467e9e8ba4a9ca3f881d,

title = "Cutting a cornered convex polygon out of a circle",

abstract = "The problem of cutting a convex polygon P 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 P 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 n is the number of vertices of P.",

keywords = "Algorithm, Circle, Computational geometry, Line cut, Polygon cutting",

author = "Ahmed, {Syed Ishtiaque} and Islam, {Md Ariful} and Masud Hasan",

year = "2008",

doi = "10.1109/ICCITECHN.2008.4802988",

language = "English",

isbn = "9781424421367",

series = "Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008",

pages = "1--6",

booktitle = "Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008",

note = "11th International Conference on Computer and Information Technology, ICCIT 2008 ; Conference date: 25-12-2008 Through 27-12-2008",

}

Ahmed, SI, Islam, MA & Hasan, M 2008, Cutting a cornered convex polygon out of a circle. in Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008., 4802988, Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008, pp. 1-6, 11th International Conference on Computer and Information Technology, ICCIT 2008, Khulna, Bangladesh, 12/25/08. https://doi.org/10.1109/ICCITECHN.2008.4802988

Cutting a cornered convex polygon out of a circle. / Ahmed, Syed Ishtiaque; Islam, Md Ariful; Hasan, Masud.
Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008. 2008. p. 1-6 4802988 (Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Cutting a cornered convex polygon out of a circle

AU - Ahmed, Syed Ishtiaque

AU - Islam, Md Ariful

AU - Hasan, Masud

PY - 2008

Y1 - 2008

N2 - The problem of cutting a convex polygon P 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 P 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 n is the number of vertices of P.

AB - The problem of cutting a convex polygon P 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 P 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 n is the number of vertices of P.

KW - Algorithm

KW - Circle

KW - Computational geometry

KW - Line cut

KW - Polygon cutting

UR - http://www.scopus.com/inward/record.url?scp=66149175682&partnerID=8YFLogxK

U2 - 10.1109/ICCITECHN.2008.4802988

DO - 10.1109/ICCITECHN.2008.4802988

M3 - Conference contribution

AN - SCOPUS:66149175682

SN - 9781424421367

T3 - Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008

SP - 1

EP - 6

BT - Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008

T2 - 11th International Conference on Computer and Information Technology, ICCIT 2008

Y2 - 25 December 2008 through 27 December 2008

ER -

Cutting a cornered convex polygon out of a circle

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this