File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Approximation of minimum triangulation for polyhedron with bounded degrees

TitleApproximation of minimum triangulation for polyhedron with bounded degrees
Authors
Issue Date2001
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2001, v. 2223 LNCS, p. 172-184 How to Cite?
AbstractFinding minimum triangulations of convex polyhedra is NPhard. The best approximation algorithms only give a ratio 2 for this problem, and for combinatorial algorithms it is shown to be the best possible asymptotically. In this paper we improve the approximation ratio of finding minimum triangulations for some special classes of 3-dimensional convex polyhedra. (1) For polyhedra without 3-cycles and degree-4 vertices we achieve a tight approximation ratio 3/2. (2) For polyhedra with vertices of degree-5 or above, we achieve an upper bound 2 - 1/12 on the approximation ratio. (3) For polyhedra with n vertices and vertex degrees bounded by a constant Δ we achieve an asymptotic tight ratio 2 - ω (1/Δ) - ω (1/n). © 2001 Springer Berlin Heidelberg.
Persistent Identifierhttp://hdl.handle.net/10722/93258
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorFung, SPYen_HK
dc.date.accessioned2010-09-25T14:55:40Z-
dc.date.available2010-09-25T14:55:40Z-
dc.date.issued2001en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2001, v. 2223 LNCS, p. 172-184en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93258-
dc.description.abstractFinding minimum triangulations of convex polyhedra is NPhard. The best approximation algorithms only give a ratio 2 for this problem, and for combinatorial algorithms it is shown to be the best possible asymptotically. In this paper we improve the approximation ratio of finding minimum triangulations for some special classes of 3-dimensional convex polyhedra. (1) For polyhedra without 3-cycles and degree-4 vertices we achieve a tight approximation ratio 3/2. (2) For polyhedra with vertices of degree-5 or above, we achieve an upper bound 2 - 1/12 on the approximation ratio. (3) For polyhedra with n vertices and vertex degrees bounded by a constant Δ we achieve an asymptotic tight ratio 2 - ω (1/Δ) - ω (1/n). © 2001 Springer Berlin Heidelberg.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleApproximation of minimum triangulation for polyhedron with bounded degreesen_HK
dc.typeConference_Paperen_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.1007/3-540-45678-3_16en_HK
dc.identifier.scopuseid_2-s2.0-23044529049en_HK
dc.identifier.hkuros65652en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-23044529049&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume2223 LNCSen_HK
dc.identifier.spage172en_HK
dc.identifier.epage184en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats