Cutting a cornered convex polygon out of a circle

Syed Ishtiaque Ahmed, Md Ariful Islam, Masud Hasan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationProceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008
Pages1-6
Number of pages6
DOIs
StatePublished - 2008
Event11th International Conference on Computer and Information Technology, ICCIT 2008 - Khulna, Bangladesh
Duration: Dec 25 2008Dec 27 2008

Publication series

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

Conference

Conference11th International Conference on Computer and Information Technology, ICCIT 2008
CountryBangladesh
CityKhulna
Period12/25/0812/27/08

Keywords

  • Algorithm
  • Circle
  • Computational geometry
  • Line cut
  • Polygon cutting

Fingerprint Dive into the research topics of 'Cutting a cornered convex polygon out of a circle'. Together they form a unique fingerprint.

  • 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). [4802988] (Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008). https://doi.org/10.1109/ICCITECHN.2008.4802988