1.6.2 Convex Hull
INPUT OUTPUT
Input Description:
A set S of n points in d-dimensional space.
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.
Recommended Books
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Computational Geometry : Algorithms and Applications
Computational Geometry in C
Algorithms from P to NP, Vol. I: Design and Efficiency
Introduction to Algorithms
