Minimum-weight triangulation is NP-hard

DOI10.1145/1346330.1346336zbMATH Open1311.05134arXivcs/0601002OpenAlexW2116909526WikidataQ130984618 ScholiaQ130984618MaRDI QIDQ3546362FDOQ3546362

Authors: Wolfgang Mulzer, Günter Rote 

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0601002

Recommendations

• Minimum weight triangulation is NP-hard
• New results for the minimum weight triangulation problem
• Parameterized and Exact Computation
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Polynomial-time instances of the minimum weight triangulation problem

Mathematics Subject Classification ID

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)

Cited In (56)

• Fast-mixed searching and related problems on graphs
• Conflict-free coloring of graphs
• Turning cliques into paths to achieve planarity
• One strike against the min-max degree triangulation problem
• Method for finding and storing optimal triangulations based on square matrix
• Planar 3-SAT with a clause/variable cycle
• The complexity of separating points in the plane
• Computing coverage kernels under restricted settings
• Title not available (Why is that?)
• Minimum weight convex Steiner partitions
• On the Complexity of Clustering with Relaxed Size Constraints
• A note on a QPTAS for maximum weight triangulation of planar point sets
• 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
• Towards an algorithmic guide to Spiral Galaxies
• On the computational complexity of the bipartizing matching problem
• Neighbour-sum-2-distinguishing edge-weightings: doubling the 1-2-3 conjecture
• Geometry and generation of a new graph planarity game
• Further results on an equitable 1-2-3 conjecture
• 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
• Solving large-scale minimum-weight triangulation instances to provable optimality
• Parameterized complexity of minimum membership dominating set
• 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
• On Proper Labellings of Graphs with Minimum Label Sum
• The complexity of Helly-\(B_1\) EPG graph recognition
• New results for the minimum weight triangulation problem
• Computing geometric minimum-dilation graphs is NP-hard
• Contact Graphs of Circular Arcs
• Conflict-free coloring of intersection graphs
• Rectangular spiral galaxies are still hard
• Conflict-free coloring of intersection graphs
• On minimum weight pseudo-triangulations
• On plane geometric spanners: a survey and open problems
• OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS
• Augmenting Geometric Graphs with Matchings
• Complexity and algorithms for recognizing polar and monopolar graphs
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Rectangle transformation problem
• On Planar Boolean CSP
• Matching colored points with rectangles
• 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
• Square Coloring Planar Graphs with Automatic Discharging
• Conflict-free coloring: graphs of bounded clique-width and intersection graphs
• Graphs whose vertices of degree at least 2 lie in a triangle
• On the \(d\)-claw vertex deletion problem

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)