Minimum-weight triangulation is NP-hard

Abstract

A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum-weight triangulation (MWT) problem, we are looking for a triangulation of a given point set that minimizes the sum of the edge lengths. We prove that the decision version of this problem is NP-hard. We use a reduction from PLANAR-1-IN-3-SAT. The correct working of the gadgets is established with computer assistance, using dynamic programming on polygonal faces, as well as the beta-skeleton heuristic to certify that certain edges belong to the minimum-weight triangulation.

45 pages (including a technical appendix of 13 pages), 28 figures. This revision contains a few improvements in the exposition

References in corpus (1)

• Minimum-weight triangulation is NP-hard

Cited by in corpus (25)

• Minimum-weight triangulation is NP-hard
• Growing Urban Bicycle Networks
• Conflict-Free Coloring of Planar Graphs
• Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small
• Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
• The Complexity of Helly-$B_1$ EPG Graph Recognition
• Contact Representations of Sparse Planar Graphs
• Geometric Multicut
• Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• On a Linear Program for Minimum-Weight Triangulation
• Optimized two-dimensional Networks with edge crossing cost: frustrated anti-ferromagnetic spin system
• $k$-best enumeration
• Reconfiguring Ordered Bases of a Matroid
• Adjacency-Preserving Spatial Treemaps
• Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality
• Being even slightly shallow makes life hard
• Planar 3-SAT with a Clause/Variable Cycle
• Turning Cliques into Paths to Achieve Planarity
• On Planar Valued CSPs
• An exact algorithm for 1-in-3 SAT
• Minimum Average Distance Triangulations
• The inverse Voronoi problem in graphs
• Near-Delaunay Metrics
• The Complexity of MaxMin Length Triangulation