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