preprocessing (to find the leftmost and rightmost vertices).

A monotone polygon may be easily triangulated in linear time.

For a given set of points in the plane, a bitonic tour is a monotone polygon that connects the points. The minimum perimeter bitonic tour for a given point set with respect to a fixed direction may be found in polynomial time using dynamic programming.

1.Previous
3.Next