Data Structures and Algorithms

Finding the Convex Hull

The Convex Hull is the line completely enclosing
a set of points in a plane so that there are no
concavities in the line.
More formally, we can describe it as the smallest convex polygon
which encloses a set of points such that each point in the set
lies within the polygon or on its perimeter.
Algorithm
Graham's scan has these steps:
 Find
p_{0},
the point with the minimum y coordinate,
 Sort all the remaining points in order of their polar
angle from
p_{0}
 Initialize a stack, S
 push(S,p_{0})
 push(S,p_{1})
 push(S,p_{2})
 for i=3 to n do
while (angle formed by topnext(S), top(S) and p_{i} makes a right turn
push(S,p_{i}
 return S
This algorithm takes O(n logn) time.
A second algorithm, known as Jarvis' march
proceeds as follows:
 Find the 'leftmost' (minimum x) and 'rightmost' (maximum x) points.
 Divide points into those above and below
the line joining these points.
 In the bottom half, starting with the leftmost point,
add the point with the least angle to the y axis from the current point
until the rightmost point is reached,
 Repeat the scan in the upper half.
This algorithm takes O(n h) time, where h is the
numer of vertices in the convex hull.
Animation
Two animations of the convex hull algorithm have been written:
Convex Hull Animation
This animation was written by KyungTae Kim
It is a prototype: volunteers to improve it are welcome! 


Convex Hull Animation
This animation was written by JiMo Jung
It is a prototype: volunteers to improve it are welcome! 


Key terms 
 convex hull
 Line enclosing a set of points in a plane with no concavities.

© John Morris, 2004