Minimum-weight triangulation
- Minimum-weight triangulation
-
In computational geometry and computer science, the minimum-weight triangulation (MWT) problem is the problem of finding a triangulation of minimal weight. Of particular interest is the problem of finding a minimum-weight point set triangulation.
Minimum-weight triangulation for a finite planar point set
The weight of a triangulation of a set of points in the Euclidean plane is defined as the sum of lengths of its edges. The computational complexity of the problem of finding an MWT for a planar point set used to be one of the long-standing open problems listed in the seminal book Computers and Intractability by Garey and Johnson. Its decision variant, i.e., the problem of deciding whether there exists a triangulation of weight less than a given weight, was proven to be NP-hard in 2006 by W. Mulzer and G. Rote. Their proof is by reduction from the PLANAR-1-IN-3-SAT[1] problem.[2]
It is not known whether it is NP-complete, since this depends on the known open problem whether the sum of radicals may be computed in polynomial time. Mulzer and Rote remark that the problem is NP-complete if the edge weights are the rounded lengths. Their result also implies the NP-hardness of finding an approximate solution with relative approximation error at most O(1/n2).
Minimum-weight triangulation for a planar polygon
A polygon triangulation of minimal weight may be constructed in cubic time using the dynamic programming approach, reported independently by Gilbert (1979) [3] and Klincsek (1980)[4].
See also
References
- ^ PLANAR-1-in-3-SAT is a special case of the Boolean satisfiability problem, in which a 3-CNF whose graph is planar is accepted if there are variable values which satisfy exactly one clause in each literal, see One-in-three 3SAT.
- ^ Wolfgang Mulzer, Günter Rote, "Minimum-Weight Triangulation Is NP-Hard", In: Proceedings of the 22nd Annual Symposium on Computational Geometry, Sedona, June 5–7, 2006, pp. 1–10; final version in Journal of the ACM, Vol. 55, No. 2, article 11, 2008.
- ^ P. D. Gilbert. New results in planar triangulations. Report R-850, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois, 1979.
- ^ G. T. Klincsek. Minimal triangulations of polygonal domains. Annals of Discrete Mathematics, volume 9, 1980, pp. 121–123.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Triangulation (Punktemenge) — Eine Triangulation einer Menge von Punkten P in der Ebene bezeichnet eine Zerlegung der konvexen Hülle der Punktmenge in Dreiecke, wobei die Eckpunkte der Dreiecke genau die Punkte aus P sind. Somit ist die Triangulation ein ebener Dreiecksgraph … Deutsch Wikipedia
Euclidean minimum spanning tree — The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of points in the plane (or more generally in Bbb{R}^n), where the weight of the edge between each pair of points is the distance between those two points. In simpler… … Wikipedia
List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… … Wikipedia
Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français
Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… … Wikipédia en Français
Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La … Wikipédia en Français
Liste de problèmes np-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive … Wikipédia en Français
Dreiecksnetz — Ein Dreiecksnetz ist ein ebener oder räumlicher Graph, der nur aus Dreiecken besteht. Das Dreieck wie auch dessen Ermittlung werden Triangulierung genannt. Dreiecksnetze werden in der Technik zur Vermessung und zur Modellierung verwendet.… … Deutsch Wikipedia
Graph isomorphism — In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly… … Wikipedia
Gitter (Geometrie) — Ein Gitter in der Geometrie ist eine lückenlose und überlappungsfreie Partition eines Bereichs des Raumes durch eine Menge von Gitterzellen. Die Gitterzellen werden definiert durch eine Menge von Gitterpunkten, die untereinander durch eine Menge… … Deutsch Wikipedia
