Minimum weight triangulation
Encyclopedia
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
.
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 problem.
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).
of minimal weight may be constructed in cubic time using the dynamic programming
approach, reported independently by Gilbert (1979) and Klincsek (1980).
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, 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
Point set triangulation
A triangulation of a set of points P in the plane is a triangulation of the convex hull of P, with all points from P being among the vertices of the triangulation. Triangulations are special cases of planar straight-line graphs....
.
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 complexityComputational Complexity
Computational Complexity may refer to:*Computational complexity theory*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
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
in 2006 by W. Mulzer and G. Rote. Their proof is by reduction
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
from the PLANAR-1-IN-3-SAT problem.
It is not known whether it is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, since this depends on the known open problem whether the sum of radicals
Sum of radicals
In computational complexity theory there is an open problem whether some information about the sum of radicals may be computed in polynomial time depending on the input size, i.e., in the number of bits necessary to represent this sum...
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 triangulationPolygon triangulation
In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
of minimal weight may be constructed in cubic time using the dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
approach, reported independently by Gilbert (1979) and Klincsek (1980).
See also
- Beta skeletonBeta skeletonIn computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane...
- Minimum Weight Triangulation using an LMT Skeleton source code'