Minimum Weight Triangulation is NP-hard

OxDE points us to a great result: Minimum Weight Triangulation is NP-hard, by Mulzer and Rote.

OxDE has more thoughts on the result. A quick perusal reveals that

• The gadget construction (the proof is via reduction from planar 1-in-3-SAT) is proved correct via computer. Depending on how picky you are about such things, the proof is therefore not "by hand" yet.
  
• MWT is still not known to be in NP, because it is not known whether the number of bits needed to express edge lengths in an optimal solution is polynomial in the input size. They claim that their result can be extended to the case when edge weights are "rounded", and thus show NP-Completeness for this case.
  

If it all checks out, it's a major result, resolving the first problem on the CG Open Problems list, as well as whittling down to two the number of problems from Garey and Johnson's original list of 1412 that lie in limbo between P and NP (Factoring Precedence-constrained 3-processor scheduling and Graph Isomorphism)

Update: There were 12 open problems, not 14, and factoring was not one of them (Thanks, Lance).

Categories

• geometry