2000/12/18 by Alexander Below, Below, Alexander, Jesús A. De Loera +3
Computer Science · Mathematics · #52B #52C45 #68Q #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems #Metric Geometry (math.MG) #math.CO #math.MG #msc:52B #msc:52C45 #msc:68Q
paper · pdf · doi:10.48550/arxiv.math/0012177
37 pages. An earlier version containing the sketch of the proof appeared at the proceedings of SODA 2000
arxiv created 2000/12/18 · openalex publication_date 2000/12/18 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.