Minimum-weight triangulation is NP-hard
From MaRDI portal
Publication:3546362
DOI10.1145/1346330.1346336zbMath1311.05134arXivcs/0601002OpenAlexW2116909526MaRDI QIDQ3546362
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0601002
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62) Polyhedral manifolds (52B70)
Related Items
On Proper Labellings of Graphs with Minimum Label Sum ⋮ Neighbour-sum-2-distinguishing edge-weightings: doubling the 1-2-3 conjecture ⋮ On Planar Boolean CSP ⋮ Contact Graphs of Circular Arcs ⋮ OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS ⋮ Parameterized complexity of minimum membership dominating set ⋮ Conflict-Free Coloring of Graphs ⋮ Unnamed Item ⋮ Conflict-Free Coloring of Intersection Graphs ⋮ On planar valued CSPs ⋮ A new asymmetric inclusion region for minimum weight triangulation ⋮ On plane geometric spanners: a survey and open problems ⋮ Fast-mixed searching and related problems on graphs ⋮ Rectangle transformation problem ⋮ On the computational complexity of the bipartizing matching problem ⋮ Rectangular spiral galaxies are still hard ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ Square Coloring Planar Graphs with Automatic Discharging ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ On the complexity of clustering with relaxed size constraints in fixed dimension ⋮ Geometric multicut: shortest fences for separating groups of objects in the plane ⋮ Complexity and algorithms for recognizing polar and monopolar graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On minimum weight pseudo-triangulations ⋮ A note on a QPTAS for maximum weight triangulation of planar point sets ⋮ Turning cliques into paths to achieve planarity ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ Matching colored points with rectangles ⋮ Binary pattern tile set synthesis is NP-hard ⋮ The inverse Voronoi problem in graphs. I: Hardness ⋮ Minimum weight convex Steiner partitions ⋮ Parameterized complexity of minimum membership dominating set ⋮ Further results on an equitable 1-2-3 conjecture ⋮ Computing coverage kernels under restricted settings ⋮ On the \(d\)-claw vertex deletion problem ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ Minimum membership covering and hitting ⋮ Unnamed Item ⋮ Maximum independent and disjoint coverage ⋮ Unnamed Item ⋮ The Voronoi diagram of three lines ⋮ On the Complexity of Clustering with Relaxed Size Constraints ⋮ Geometry and Generation of a New Graph Planarity Game ⋮ Unnamed Item ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Unnamed Item ⋮ Augmenting Geometric Graphs with Matchings ⋮ Towards an algorithmic guide to Spiral Galaxies ⋮ On proper labellings of graphs with minimum label sum ⋮ The complexity of separating points in the plane
