File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/3-540-45678-3_16
- Scopus: eid_2-s2.0-23044529049
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Approximation of minimum triangulation for polyhedron with bounded degrees
Title | Approximation of minimum triangulation for polyhedron with bounded degrees |
---|---|
Authors | |
Issue Date | 2001 |
Publisher | Springer 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? |
Abstract | Finding 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 Identifier | http://hdl.handle.net/10722/93258 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Fung, SPY | en_HK |
dc.date.accessioned | 2010-09-25T14:55:40Z | - |
dc.date.available | 2010-09-25T14:55:40Z | - |
dc.date.issued | 2001 | en_HK |
dc.identifier.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 | en_HK |
dc.identifier.issn | 0302-9743 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93258 | - |
dc.description.abstract | Finding 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.language | eng | en_HK |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en_HK |
dc.title | Approximation of minimum triangulation for polyhedron with bounded degrees | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/3-540-45678-3_16 | en_HK |
dc.identifier.scopus | eid_2-s2.0-23044529049 | en_HK |
dc.identifier.hkuros | 65652 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-23044529049&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 2223 LNCS | en_HK |
dc.identifier.spage | 172 | en_HK |
dc.identifier.epage | 184 | en_HK |
dc.publisher.place | Germany | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Fung, SPY=7201970079 | en_HK |
dc.identifier.issnl | 0302-9743 | - |