Minimum weight triangulation is NP-hard
From MaRDI portal
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)
Recommendations
Cited in
(15)- On piecewise linear approximations of bilinear terms: structural comparison of univariate and bivariate mixed-integer programming formulations
- An almost four-approximation algorithm for maximum weight triangulation
- Solving large-scale minimum-weight triangulation instances to provable optimality
- Minimum weight pseudo-triangulations
- Optimization for first order Delaunay triangulations
- Steiner reducing sets of minimum weight triangulations: Structure and topology
- A linear time algorithm for max-min length triangulation of a convex polygon
- Simulated Annealing and Genetic Algorithms in Quest of Optimal Triangulations
- Minimum-weight triangulation is NP-hard
- Algorithms and Computation
- Optimal Higher Order Delaunay Triangulations of Polygons
- Decomposing a simple polygon into pseudo-triangles and convex polygons
- A quasi-polynomial time approximation scheme for minimum weight triangulation
- A fixed parameter algorithm for optimal convex partitions
- Optimal higher order Delaunay triangulations of 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)
