File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Approximation for minimum triangulation of convex polyhedra

TitleApproximation for minimum triangulation of convex polyhedra
Authors
Chin, FYLFung, SPYWang, CA
KeywordsAlgorithms
Design
Measurement
Performance
Theory
Verification
Issue Date2001
PublisherSociety for Industrial and Applied Mathematics.
Citation
The Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington, DC, 7-9 January 2001. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, p. 128-137 How to Cite?
AbstractThe minimum triangulation of a convex polyhedron is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding the minimum triangulation of convex polyhedra 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 - &OHgr;(l/√). We also show that this is best possible for algorithms that only consider the combinatorial structure of the polyhedra. Copyright © 2009 ACM, Inc.
Persistent Identifierhttp://hdl.handle.net/10722/45628
ISSN
1071-9040
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorFung, SPYen_HK
dc.contributor.authorWang, CAen_HK
dc.date.accessioned2007-10-30T06:30:37Z-
dc.date.available2007-10-30T06:30:37Z-
dc.date.issued2001en_HK
dc.identifier.citationThe Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington, DC, 7-9 January 2001. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, p. 128-137en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45628-
dc.description.abstractThe minimum triangulation of a convex polyhedron is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding the minimum triangulation of convex polyhedra 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 - &OHgr;(l/√). We also show that this is best possible for algorithms that only consider the combinatorial structure of the polyhedra. Copyright © 2009 ACM, Inc.en_HK
dc.format.extent594942 bytes-
dc.format.extent5052 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofProceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rights© 2001 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms in 2001, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectAlgorithmsen_HK
dc.subjectDesignen_HK
dc.subjectMeasurementen_HK
dc.subjectPerformanceen_HK
dc.subjectTheoryen_HK
dc.subjectVerificationen_HK
dc.titleApproximation for minimum triangulation of convex polyhedraen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.scopuseid_2-s2.0-48549099846en_HK
dc.identifier.hkuros57601-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-48549099846&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage128en_HK
dc.identifier.epage137en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.scopusauthoridWang, CA=8895045600en_HK
dc.identifier.issnl1071-9040-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats