INPUT OUTPUT

**Problem:**
Find the smallest convex polygon containing
all the points of *S*.

**Excerpt from**
The Algorithm Design Manual:
Finding the convex hull of a set of points is *the* most elementary interesting problem in computational
geometry, just as minimum spanning tree is the most elementary interesting problem in graph algorithms. It arises
because the hull quickly captures a rough idea of the shape or extent of a data set.

Convex hull also serves as a first preprocessing step to many, if not most, geometric algorithms. For example,
consider the problem of finding the diameter of a set of points, which is the pair of points a maximum distance
apart. The diameter will always be the distance between two points on the convex hull.
The *O(n \lg n)*. algorithm for computing diameter proceeds by first constructing the convex hull, then
for each hull vertex finding which other hull vertex
is farthest away from it.
This so-called ``rotating-calipers'' method can be used to move efficiently
from one hull vertex to another.

Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf | Computational Geometry in C by Joseph O'Rourke | Algorithms from P to NP, Vol. I: Design and Efficiency by B. Moret and H. Shapiro |

Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein |

This page last modified on 2008-07-10 . www.algorist.com