of pairs of integers giving the
coordinates of n points in the plane.
A triangulation of the set of points represented by C, i.e., a collection E
of non-intersecting line segments each joining two points in C that divides
the interior of the convex hull into triangular regions.
The discrete-Euclidean length of the triangulation, i.e.,
Note that the problem is not known to be NP-complete.
The Steiner variation in which the point set of E must be a superset of C
is approximable within 316 .
Triangulating planar graphs while minimizing the maximum degree is
approximable so that the maximum degree is bounded by
for general graphs and
for triconnected graphs, where
is the degree of the graph .