Finding minimal triangulations of convex 3-polytopes is NP-hard.

Alexander Below Jesús A. De Loera Jürgen Richter-Gebert

Published in: SODA (2000)

Keyphrases

np hard
convex hull
np complete
scheduling problem
optimal solution
approximation algorithms
worst case
linear programming
convex optimization
special case
greedy heuristic
np hardness
set cover
lattice points
database
search algorithm
integer programming
piecewise linear
packing problem
polynomial time approximation