Minimum-weight triangulation is NP-hard
From MaRDI portal
Graph representations (geometric and intersection representations, etc.) (05C62) Polyhedral manifolds (52B70) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
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.
Recommendations
Cited in
(63)- The Voronoi diagram of three lines
- New results for the minimum weight triangulation problem
- Neighbour-sum-2-distinguishing edge-weightings: doubling the 1-2-3 conjecture
- On the complexity of clustering with relaxed size constraints in fixed dimension
- Turning cliques into paths to achieve planarity
- Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
- The inverse Voronoi problem in graphs. I: Hardness
- Further results on an equitable 1-2-3 conjecture
- On proper labellings of graphs with minimum label sum
- Parameterized complexity of minimum membership dominating set
- Geometric multicut: shortest fences for separating groups of objects in the plane
- Towards an algorithmic guide to Spiral Galaxies
- On planar valued CSPs
- Rectangle transformation problem
- Complexity and algorithms for recognizing polar and monopolar graphs
- A note on a QPTAS for maximum weight triangulation of planar point sets
- The complexity of separating points in the plane
- A new asymmetric inclusion region for minimum weight triangulation
- On the computational complexity of the bipartizing matching problem
- Rectangular spiral galaxies are still hard
- On the Complexity of Clustering with Relaxed Size Constraints
- The complexity of Helly-B₁ EPG graph recognition
- On Planar Boolean CSP
- Contact Graphs of Circular Arcs
- Computing geometric minimum-dilation graphs is NP-hard
- On plane geometric spanners: a survey and open problems
- Minimum weight triangulation is NP-hard
- Fast-mixed searching and related problems on graphs
- Conflict-free coloring of graphs
- Conflict-free coloring of intersection graphs
- Method for finding and storing optimal triangulations based on square matrix
- Augmenting Geometric Graphs with Matchings
- On Proper Labellings of Graphs with Minimum Label Sum
- scientific article; zbMATH DE number 7204413 (Why is no real title available?)
- Solving large-scale minimum-weight triangulation instances to provable optimality
- Planar 3-SAT with a clause/variable cycle
- Matching colored points with rectangles
- Conflict-free coloring of intersection graphs
- Geometry and generation of a new graph planarity game
- OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS
- Minimum weight convex Steiner partitions
- On a linear program for minimum-weight triangulation
- A quasi-polynomial time approximation scheme for minimum weight triangulation
- Minimum membership covering and hitting
- Maximum independent and disjoint coverage
- Computing coverage kernels under restricted settings
- The Complexity of Drawing Graphs on Few Lines and Few Planes
- Parameterized complexity of minimum membership dominating set
- Edge sparsification for geometric tour problems
- Square Coloring Planar Graphs with Automatic Discharging
- An ETH-Tight Exact Algorithm for Euclidean TSP
- On the \(d\)-claw vertex deletion problem
- Conflict-free coloring: graphs of bounded clique-width and intersection graphs
- Graphs whose vertices of degree at least 2 lie in a triangle
- Computing diverse and nice triangulations
- Optimal area polygonisation problems: mixed integer linear programming models
- One strike against the min-max degree triangulation problem
- Minimum-membership geometric dominating set: complexity and algorithms
- Sparse polynomial matrix optimization
- Packing squares into a disk with optimal worst-case density
- Exact algorithms for minimum dilation triangulation
- Incremental algorithm and local search for minimum non-obtuse triangulations (CG challenge)
- On minimum weight pseudo-triangulations
This page was built for publication: Minimum-weight triangulation is NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546362)
