• DocumentCode
    3012122
  • Title

    Cutting a cornered convex polygon out of a circle

  • Author

    Ahmed, S.I. ; Islam, Ahmed Ariful ; Hasan, Masud

  • Author_Institution
    Dept. of Comput. Sci. & Eng., Bangladesh Univ. of Eng. & Technol., Dhaka
  • fYear
    2008
  • fDate
    24-27 Dec. 2008
  • Firstpage
    1
  • Lastpage
    6
  • 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
    approximation theory; computational geometry; approximation algorithm; computational geometry; cornered convex polygon; minimum total cutting length; Approximation algorithms; Computational geometry; Computer science; Costs; Information technology; Paper technology; Polynomials; Algorithm; circle; computational geometry; line cut; polygon cutting;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computer and Information Technology, 2008. ICCIT 2008. 11th International Conference on
  • Conference_Location
    Khulna
  • Print_ISBN
    978-1-4244-2135-0
  • Electronic_ISBN
    978-1-4244-2136-7
  • Type

    conf

  • DOI
    10.1109/ICCITECHN.2008.4802988
  • Filename
    4802988