Gift wrapping algorithm
From Wikipedia, the free encyclopedia
The gift wrapping algorithm is a simple algorithm for computing the convex hull of a given set of points.
[edit] Planar case
In the two-dimensional case the algorithm is also known as Jarvis march, by the name of the author, and has O(nh) time complexity, where n is the number of points and h is the number of points on the convex hull. Its real-life performance compared with other convex hull algorithms is favorable when n is small or h is expected to be very small with respect to n. In general case the algorithm is outperformed by many others.
The gift wrapping algorithm begins with i=0 and a point p0 known to be on the convex hull, e.g., the leftmost point, and selects the point pi+1 such that all points are to the right of the line pi pi+1. This point may be found on O(n) time by comparing polar angles of all points with respect to point p0 taken for the center of polar coordinates. Letting i=i+1, and repeating with until one reaches ph=p0 again yields the convex hull in h steps. The gift wrapping algorithm is exactly analogous to the process of winding a string (or wrapping paper) around the set of points.
def jarvis(P)
i = 0
p[0] = leftmost point of P
do
p[i+1] = point such that all other points in P are to the
right of the line p[i]p[i+1]
i = i + 1
while p[i] != p[0]
return p
The approach is extendable to higher dimensions.
[edit] References
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 955–956 of section 33.3: Finding the convex hull.
