Cutting a cornered convex polygon out of a circle

Syed Ishtiaque Ahmed, Md Ariful Islam, Masud Hasan

Research output: Contribution to journalArticle

5 Scopus citations

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).

Original languageEnglish
Pages (from-to)4-11
Number of pages8
JournalJournal of Computers
Volume5
Issue number1
DOIs
StatePublished - Jan 2010

Keywords

  • Algorithms
  • Approximation algorithms
  • Computational geometry
  • Line cut
  • Polygon cutting
  • Ray cut
  • Rotating calipers

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

  • Cite this