File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximation for minimum triangulations of simplicial convex 3-polytopes

TitleApproximation for minimum triangulations of simplicial convex 3-polytopes
Authors
Chin, FYLFung, SPYWang, CA
Issue Date2001
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htm
Citation
Discrete And Computanional Geometry, 2001, v. 26 n. 4, p. 499-511 How to Cite?
DOI: http://dx.doi.org/10.1007/s00454-001-0045-8
AbstractA minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm with an improved approximation ratio 2 - Ω(1/√n), where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider the combinatorial structure of the polytopes.
Persistent Identifierhttp://hdl.handle.net/10722/88890
ISSN
0179-5376
2021 Impact Factor: 0.639
2020 SCImago Journal Rankings: 0.645
ISI Accession Number ID
WOS:000171995400003
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorFung, SPYen_HK
dc.contributor.authorWang, CAen_HK
dc.date.accessioned2010-09-06T09:49:45Z-
dc.date.available2010-09-06T09:49:45Z-
dc.date.issued2001en_HK
dc.identifier.citationDiscrete And Computanional Geometry, 2001, v. 26 n. 4, p. 499-511en_HK
dc.identifier.issn0179-5376en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88890-
dc.description.abstractA minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm with an improved approximation ratio 2 - Ω(1/√n), where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider the combinatorial structure of the polytopes.en_HK
dc.languageengen_HK
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htmen_HK
dc.relation.ispartofDiscrete and Computanional Geometryen_HK
dc.titleApproximation for minimum triangulations of simplicial convex 3-polytopesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0179-5376&volume=26&issue=4&spage=499&epage=511&date=2001&atitle=Approximation+for+Minimum+Triangulations+of+Simplicial+Convex+3-Polytopesen_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/s00454-001-0045-8-
dc.identifier.scopuseid_2-s2.0-0035630043en_HK
dc.identifier.hkuros65651en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0035630043&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume26en_HK
dc.identifier.issue4en_HK
dc.identifier.spage499en_HK
dc.identifier.epage511en_HK
dc.identifier.isiWOS:000171995400003-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.scopusauthoridWang, CA=7501646353en_HK
dc.identifier.issnl0179-5376-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats