The Complexity of Finding Small Triangulations of Convex 3-Polytopes

, &

Abstract

The problem of finding a triangulation of a convex three-dimensional polytope with few tetrahedra is proved to be NP-hard. We discuss other related complexity results.

Categories

Add categories

Keywords

Reprint years

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,219

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

My notes

Similar books and articles

Extremal properties for dissections of convex 3-polytopes.A. De Loera Jesús, Santos Francisco & Takeuchi Fumihiko - unknown
Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index.Sakander Hayat, Asad Khan, Suliman Khan & Jia-Bao Liu - 2021 - Complexity 2021:1-23.
Fat 4-polytopes and fatter 3-spheres.Eppstein David, Kuperberg Greg & M. Ziegler Günter - unknown
A generalization of Filliman duality.Kuperberg Greg - unknown
The Computational Complexity of Knot Genus and Spanning Area.Agol Ian, Hass Joel & P. Thurston William - unknown
Convex Matroid Optimization.Onn Shmuel - unknown
On Computation of Recently Defined Degree-Based Topological Indices of Some Families of Convex Polytopes via M-Polynomial.Deeba Afzal, Farkhanda Afzal, Mohammad Reza Farahani & Samia Ali - 2021 - Complexity 2021:1-11.
The complexity of recursive constraint satisfaction problems.Victor W. Marek & Jeffrey B. Remmel - 2010 - Annals of Pure and Applied Logic 161 (3):447-457.
On the complexity of the pancake problem.Fuxiang Yu - 2007 - Mathematical Logic Quarterly 53 (4):532-546.
On the complexity of finding paths in a two-dimensional domain I: Shortest paths.Arthur W. Chou & Ker-I. Ko - 2004 - Mathematical Logic Quarterly 50 (6):551-572.

Analytics

Added to PP
2017-06-17

Downloads
4 (#1,805,339)

6 months
3 (#1,477,354)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references