Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Minimum-weight triangulation
open-in-new
<p>In <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a> and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the minimum-weight triangulation problem is the problem of finding a <a href="/facts/Triangulation_(geometry)/enYNhLNy">triangulation</a> of minimal total <a href="/facts/Edge_(geometry)/3lFN6sEz">edge</a> length. That is, an input polygon or the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> 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 <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> 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. </p>