The Complexity of Finding Small Triangulations of Convex 3-Polytopes

Alexander Below (Informatik ETH-Zurich); Davis); Jes\'us A. De Loera (Univ. of California; J\"urgen Richter-Gebert (Informatik ETH-Zurich)

arxiv: math/0012177 · v1 · submitted 2000-12-18 · 🧮 math.CO · math.MG

The Complexity of Finding Small Triangulations of Convex 3-Polytopes

Alexander Below (Informatik ETH-Zurich) , Jes\'us A. De Loera (Univ. of California , Davis) , J\"urgen Richter-Gebert (Informatik ETH-Zurich) This is my paper

classification 🧮 math.CO math.MG

keywords complexityconvexfindingdiscussnp-hardotherpolytopepolytopes

0 comments

read the original 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.

This paper has not been read by Pith yet.

The Complexity of Finding Small Triangulations of Convex 3-Polytopes

discussion (0)