The Complexity of Finding Small Triangulations of Convex 3-Polytopes

Simple item page
dc.creatorBelow, Alexander
dc.creatorDe Loera, Jesús A.
dc.creatorRichter-Gebert, Jürgen
dc.date2000-12-18
dc.date.accessioned2026-07-07T04:39:17Z
dc.date.available2026-07-07T04:39:17Z
dc.descriptionThe 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.
dc.description37 pages. An earlier version containing the sketch of the proof appeared at the proceedings of SODA 2000
dc.identifierhttps://arxiv.org/abs/math/0012177
dc.identifierhttp://arxiv.org/abs/math/0012177
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/60602
dc.subjectCombinatorics
dc.subjectMetric Geometry
dc.subject52B; 52C45; 68Q
dc.titleThe Complexity of Finding Small Triangulations of Convex 3-Polytopes
dc.typetext

Files

Collections

arXiv