Minimum-weight triangulation
In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.
Approximation algorithms for the minimum-weight triangulation problemBeta skeletonComputer-assisted proofComputers and IntractabilityConvex positionList of numerical analysis topicsMatthew T. DickersonMinimum weightMinimum weight triangulationPlanar SATPoint-set triangulationPolygon partitionPolygon triangulationSum of radicalsTriangulation (geometry)
Link from a Wikipage to another Wikipage
primaryTopic
Minimum-weight triangulation
In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.
has abstract
En geometría computacional, se ...... veces la triangulación óptima.
@es
In computational geometry and ...... led the optimal triangulation.
@en
Link from a Wikipage to an external page
Wikipage page ID
22,231,180
page length (characters) of wiki page
Wikipage revision ID
1,021,595,518
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
hypernym
type
comment
En geometría computacional, se ...... veces la triangulación óptima.
@es
In computational geometry and ...... led the optimal triangulation.
@en
label
Minimum-weight triangulation
@en
Triangulación de peso mínimo
@es