Data Structures and Algorithms

Optimal Triangulation

Triangulation  dividing a surface up into a set of triangles 
is the first step in the solution of a number of engineering
problems:
thus finding optimal triangulations is an important problem
in itself.
Problem
Any polygon can be divided into triangles.
The problem is to find the optimum triangulationi of
a convex polygon based on
some criterion,
eg a triangulation which minimises the perimeters of the
component triangles.
Reference
Cormen, Section 16.4
Key terms 
 convex polygon
 a convex polygon is one in which any chord joining two vertices
of the polygon lies either wholly within or on the boundary
of the polygon.

© John Morris, 1998