File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximating the minimum triangulation of convex 3-polytopes with bounded degrees

TitleApproximating the minimum triangulation of convex 3-polytopes with bounded degrees
Authors
KeywordsApproximation algorithms
Convex 3-polytopes
Minimum triangulation
Issue Date2005
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/comgeo
Citation
Computational Geometry: Theory And Applications, 2005, v. 32 n. 1, p. 1-12 How to Cite?
AbstractFinding minimum triangulations of convex 3-polytopes is NP-hard. The best approximation algorithms only give an approximation ratio of 2 for this problem, which is the best possible asymptotically when only combinatorial structures of the polytopes are considered. In this paper we improve the approximation ratio of finding minimum triangulations for some special classes of 3-dimensional convex polytopes. (1) For polytopes without 3-cycles and degree-4 vertices we achieve a tight approximation ratio of 3/2. (2) For polytopes where all vertices have degrees at least 5, we achieve an upper bound of 2-112 on the approximation ratio. (3) For polytopes with n vertices and vertex degrees bounded above by Δ we achieve an asymptotic tight ratio of 2-Ω(1/Δ)-Ω(Δ/n). When Δ is constant the ratio can be shown to be at most 2-2/(Δ+1). © 2005 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/89093
ISSN
2015 Impact Factor: 0.589
2015 SCImago Journal Rankings: 0.766
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorFung, SPYen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorPoon, CKen_HK
dc.date.accessioned2010-09-06T09:52:18Z-
dc.date.available2010-09-06T09:52:18Z-
dc.date.issued2005en_HK
dc.identifier.citationComputational Geometry: Theory And Applications, 2005, v. 32 n. 1, p. 1-12en_HK
dc.identifier.issn0925-7721en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89093-
dc.description.abstractFinding minimum triangulations of convex 3-polytopes is NP-hard. The best approximation algorithms only give an approximation ratio of 2 for this problem, which is the best possible asymptotically when only combinatorial structures of the polytopes are considered. In this paper we improve the approximation ratio of finding minimum triangulations for some special classes of 3-dimensional convex polytopes. (1) For polytopes without 3-cycles and degree-4 vertices we achieve a tight approximation ratio of 3/2. (2) For polytopes where all vertices have degrees at least 5, we achieve an upper bound of 2-112 on the approximation ratio. (3) For polytopes with n vertices and vertex degrees bounded above by Δ we achieve an asymptotic tight ratio of 2-Ω(1/Δ)-Ω(Δ/n). When Δ is constant the ratio can be shown to be at most 2-2/(Δ+1). © 2005 Elsevier B.V. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/comgeoen_HK
dc.relation.ispartofComputational Geometry: Theory and Applicationsen_HK
dc.rightsComputational Geometry. Copyright © Elsevier BV.en_HK
dc.subjectApproximation algorithmsen_HK
dc.subjectConvex 3-polytopesen_HK
dc.subjectMinimum triangulationen_HK
dc.titleApproximating the minimum triangulation of convex 3-polytopes with bounded degreesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0925-7721&volume=32&issue=1&spage=1&epage=12&date=2005&atitle=Approximating+the+minimum+triangulation+of+convex+3-polytopes+with+bounded+degreesen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.comgeo.2005.03.001en_HK
dc.identifier.scopuseid_2-s2.0-22544484811en_HK
dc.identifier.hkuros102714en_HK
dc.identifier.volume32en_HK
dc.identifier.issue1en_HK
dc.identifier.spage1en_HK
dc.identifier.epage12en_HK
dc.identifier.isiWOS:000230985700001-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridPoon, CK=7202673523en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats