Cutting a convex polyhedron out of a sphere

Syed Ishtiaque Ahmed, Masud Hasan, Md Ariful Islam

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

1 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(log2 n) times the optimal.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 4th International Workshop, WALCOM 2010, Proceedings
Pages94-101
Number of pages8
DOIs
StatePublished - 2010
Event4th International Workshop on Algorithms and Computation, WALCOM 2010 - Dhaka, Bangladesh
Duration: Feb 10 2010 → Feb 12 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5942 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Workshop on Algorithms and Computation, WALCOM 2010
CountryBangladesh
CityDhaka
Period02/10/10 → 02/12/10

Keywords

  • Approximation algorithm
  • Guillotine cut
  • Polyhedra cutting

Access to Document

Fingerprint Dive into the research topics of 'Cutting a convex polyhedron out of a sphere'. Together they form a unique fingerprint.

    • Cite this

    Ahmed, S. I., Hasan, M., & Islam, M. A. (2010). Cutting a convex polyhedron out of a sphere. In WALCOM: Algorithms and Computation - 4th International Workshop, WALCOM 2010, Proceedings (pp. 94-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5942 LNCS). https://doi.org/10.1007/978-3-642-11440-3_9