Minimum weight triangulation is NP-hard
From MaRDI portal
Graph representations (geometric and intersection representations, etc.) (05C62) Polyhedral manifolds (52B70) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Recommendations
Cited in
(15)- A fixed parameter algorithm for optimal convex partitions
- Optimal higher order Delaunay triangulations of polygons
- An almost four-approximation algorithm for maximum weight triangulation
- Optimization for first order Delaunay triangulations
- Minimum weight pseudo-triangulations
- On piecewise linear approximations of bilinear terms: structural comparison of univariate and bivariate mixed-integer programming formulations
- Minimum-weight triangulation is NP-hard
- Simulated Annealing and Genetic Algorithms in Quest of Optimal Triangulations
- Solving large-scale minimum-weight triangulation instances to provable optimality
- Optimal Higher Order Delaunay Triangulations of Polygons
- Algorithms and Computation
- A quasi-polynomial time approximation scheme for minimum weight triangulation
- A linear time algorithm for max-min length triangulation of a convex polygon
- Steiner reducing sets of minimum weight triangulations: Structure and topology
- Decomposing a simple polygon into pseudo-triangles and convex polygons
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 Q3601515)
