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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Triangulación de peso mínimo (es)
- Minimum-weight triangulation (en)
|
| rdfs:comment
| - 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. (es)
- 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. (en)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - 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. (es)
- 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. (en)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
