Minimum-weight triangulation
http://dbpedia.org/resource/Minimum-weight_triangulation an entity of type: WikicatNP-hardProblems
En geometría computacional, se denomina problema de triangulación de peso mínimo (Minimum-weight triangulation o MWT) al problema de encontrar una triangulación de longitud de borde total mínima. Es decir, dado un polígono de entrada (o el cierre convexo de un conjunto de puntos de la entrada) encontrar la subdivisión del mismo en triángulos adyacentes, de tal manera que se minimice la suma de los perímetros de los triángulos. El problema es NP-duro para entradas consistentes en conjuntos de puntos, pero puede ser aproximado con cualquier grado deseado de exactitud. Si la entrada consiste en un polígono, puede ser solucionado exactamente en tiempo polinómico. La triangulación de peso mínimo también se ha denominado a veces la triangulación óptima.
rdf:langString
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.
rdf:langString
rdf:langString
Triangulación de peso mínimo
rdf:langString
Minimum-weight triangulation
xsd:integer
22231180
xsd:integer
1117724395
rdf:langString
En geometría computacional, se denomina problema de triangulación de peso mínimo (Minimum-weight triangulation o MWT) al problema de encontrar una triangulación de longitud de borde total mínima. Es decir, dado un polígono de entrada (o el cierre convexo de un conjunto de puntos de la entrada) encontrar la subdivisión del mismo en triángulos adyacentes, de tal manera que se minimice la suma de los perímetros de los triángulos. El problema es NP-duro para entradas consistentes en conjuntos de puntos, pero puede ser aproximado con cualquier grado deseado de exactitud. Si la entrada consiste en un polígono, puede ser solucionado exactamente en tiempo polinómico. La triangulación de peso mínimo también se ha denominado a veces la triangulación óptima.
rdf:langString
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.
xsd:nonNegativeInteger
29657
