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.

Continue on to Graph Algorithms Back to the Table of Contents
© John Morris, 1998