Cutting a Convex Polyhedron Out of a Sphere

Syed Ishtiaque Ahmed, Masud Hasan, Md Ariful Islam

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

Given a convex polyhedron P of n vertices inside a sphere Q, we give an O(n3)-time algorithm that cuts P out of Q by using guillotine cuts and has cutting cost O(log2n) times the optimal.

Original languageEnglish
Pages (from-to)307-319
Number of pages13
JournalGraphs and Combinatorics
Volume27
Issue number3
DOIs
StatePublished - May 2011

Keywords

  • Approximation algorithm
  • Guillotine cut
  • Polyhedra cutting

Fingerprint Dive into the research topics of 'Cutting a Convex Polyhedron Out of a Sphere'. Together they form a unique fingerprint.

Cite this