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, OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS, Unnamed Item, 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, 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 Complexity of Clustering with Relaxed Size Constraints, On Planar Boolean CSP, Contact Graphs of Circular Arcs, COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD
