Cutting a convex polyhedron out of a sphere

Syed Ishtiaque Ahmed; Masud Hasan; Md Ariful Islam

doi:10.1007/978-3-642-11440-3_9

Cutting a convex polyhedron out of a sphere

Syed Ishtiaque Ahmed, Masud Hasan, Md Ariful Islam

Computer Science

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

1 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
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - 4th International Workshop, WALCOM 2010, Proceedings
Pages	94-101
Number of pages	8
DOIs	https://doi.org/10.1007/978-3-642-11440-3_9
State	Published - 2010
Event	4th International Workshop on Algorithms and Computation, WALCOM 2010 - Dhaka, Bangladesh Duration: Feb 10 2010 → Feb 12 2010

Publication series

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

Conference

Conference	4th International Workshop on Algorithms and Computation, WALCOM 2010
Country/Territory	Bangladesh
City	Dhaka
Period	02/10/10 → 02/12/10

Keywords

Approximation algorithm
Guillotine cut
Polyhedra cutting

Access to Document

10.1007/978-3-642-11440-3_9

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

@inproceedings{016d4971119b449287fbc7f091c6af04,

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

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

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

year = "2010",

doi = "10.1007/978-3-642-11440-3_9",

language = "English",

isbn = "3642114393",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "94--101",

booktitle = "WALCOM",

note = "4th International Workshop on Algorithms and Computation, WALCOM 2010 ; Conference date: 10-02-2010 Through 12-02-2010",

}

Ahmed, SI, Hasan, M & Islam, MA 2010, Cutting a convex polyhedron out of a sphere. in WALCOM: Algorithms and Computation - 4th International Workshop, WALCOM 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5942 LNCS, pp. 94-101, 4th International Workshop on Algorithms and Computation, WALCOM 2010, Dhaka, Bangladesh, 02/10/10. https://doi.org/10.1007/978-3-642-11440-3_9

Cutting a convex polyhedron out of a sphere. / Ahmed, Syed Ishtiaque; Hasan, Masud; Islam, Md Ariful.
WALCOM: Algorithms and Computation - 4th International Workshop, WALCOM 2010, Proceedings. 2010. p. 94-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5942 LNCS).

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

TY - GEN

T1 - Cutting a convex polyhedron out of a sphere

AU - Ahmed, Syed Ishtiaque

AU - Hasan, Masud

AU - Islam, Md Ariful

PY - 2010

Y1 - 2010

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

KW - Approximation algorithm

KW - Guillotine cut

KW - Polyhedra cutting

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

U2 - 10.1007/978-3-642-11440-3_9

DO - 10.1007/978-3-642-11440-3_9

M3 - Conference contribution

AN - SCOPUS:77949596846

SN - 3642114393

SN - 9783642114397

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 94

EP - 101

BT - WALCOM

T2 - 4th International Workshop on Algorithms and Computation, WALCOM 2010

Y2 - 10 February 2010 through 12 February 2010

ER -

Cutting a convex polyhedron out of a sphere

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this