|
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