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 prrof 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.
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.