Abstract
Finding 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.
| Original language | English |
|---|---|
| Pages (from-to) | 1-12 |
| Journal | Computational Geometry: Theory and Applications |
| Volume | 32 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Sept 2005 |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Funding
The research described in this paper was fully supported by two grants from the Research Grants Council of the Hong Kong SAR, China [HKU 7019/00E and CityU 1198/03E].
Research Keywords
- Approximation algorithms
- Convex 3-polytopes
- Minimum triangulation
RGC Funding Information
- RGC-funded
Fingerprint
Dive into the research topics of 'Approximating the minimum triangulation of convex 3-polytopes with bounded degrees'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver