Minimum-weight triangulation is NP-hard
From MaRDI portal
Publication:3546362
DOI10.1145/1346330.1346336zbMath1311.05134arXivcs/0601002MaRDI 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
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
65D18: Numerical aspects of computer graphics, image analysis, and computational geometry
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C62: Graph representations (geometric and intersection representations, etc.)
52B70: Polyhedral manifolds
Related Items
Conflict-Free Coloring of Graphs, Unnamed Item, Conflict-Free Coloring of Intersection Graphs, Unnamed Item, Unnamed Item, Unnamed Item, Augmenting Geometric Graphs with Matchings, On Proper Labellings of Graphs with Minimum Label Sum, Geometry and Generation of a New Graph Planarity Game, Planar 3-SAT with a clause/variable cycle, OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS, Unnamed Item, Computing coverage kernels under restricted settings, Minimum membership covering and hitting, Maximum independent and disjoint coverage, Unnamed Item, Parameterized complexity of minimum membership dominating set, On the \(d\)-claw vertex deletion problem, 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, The complexity of separating points in the plane, On plane geometric spanners: a survey and open problems, Fast-mixed searching and related problems on graphs, Matching colored points with rectangles, Binary pattern tile set synthesis is NP-hard, Minimum weight convex Steiner partitions, On minimum weight pseudo-triangulations, The Voronoi diagram of three lines, 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, 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, Unnamed Item, On Planar Boolean CSP, Contact Graphs of Circular Arcs, COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD
