MINIMUM LENGTH TRIANGULATION

• INSTANCE: Collection $C=\{(a_i,b_i) : 1 \leq i \leq n\}$ of pairs of integers giving the coordinates of n points in the plane.

• SOLUTION: 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.

• MEASURE: The discrete-Euclidean length of the triangulation, i.e.,
  
  $$\left\lceil\sum_{((a_i,b_i),(a_j,b_j)) \in E}\sqrt{(a_i-a_j)^2+(b_i-b_j)^2}\right\rceil.$$
  
  

  
  

• Good News: In APX [353].

• Comment: 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 [144].

  Triangulating planar graphs while minimizing the maximum degree is approximable so that the maximum degree is bounded by $3\Delta/2+11$ for general graphs and $\Delta+8$ for triconnected graphs, where $\Delta$ is the degree of the graph [288].

• Garey and Johnson: OPEN12