Cutting a Convex Polyhedron Out of a Sphere

Syed Ishtiaque Ahmed; Masud Hasan; Md Ariful Islam

doi:10.1007/s00373-011-1018-1

Cutting a Convex Polyhedron Out of a Sphere

Syed Ishtiaque Ahmed, Masud Hasan, Md Ariful Islam

Computer Science

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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

Original language	English
Pages (from-to)	307-319
Number of pages	13
Journal	Graphs and Combinatorics
Volume	27
Issue number	3
DOIs	https://doi.org/10.1007/s00373-011-1018-1
State	Published - May 2011

Keywords

Approximation algorithm
Guillotine cut
Polyhedra cutting

Access to Document

10.1007/s00373-011-1018-1

Cite this

@article{d5acf7b774cb4b30af79912374e43f32,

title = "Cutting a Convex Polyhedron Out of a Sphere",

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.",

keywords = "Approximation algorithm, Guillotine cut, Polyhedra cutting",

author = "Ahmed, {Syed Ishtiaque} and Masud Hasan and Islam, {Md Ariful}",

year = "2011",

month = may,

doi = "10.1007/s00373-011-1018-1",

language = "English",

volume = "27",

pages = "307--319",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

number = "3",

}

TY - JOUR

T1 - Cutting a Convex Polyhedron Out of a Sphere

AU - Ahmed, Syed Ishtiaque

AU - Hasan, Masud

AU - Islam, Md Ariful

PY - 2011/5

Y1 - 2011/5

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

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

KW - Approximation algorithm

KW - Guillotine cut

KW - Polyhedra cutting

UR - http://www.scopus.com/inward/record.url?scp=79954630322&partnerID=8YFLogxK

U2 - 10.1007/s00373-011-1018-1

DO - 10.1007/s00373-011-1018-1

M3 - Article

AN - SCOPUS:79954630322

SN - 0911-0119

VL - 27

SP - 307

EP - 319

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

ER -

Cutting a Convex Polyhedron Out of a Sphere

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this