Gift wrapping algorithm

The gift wrapping algorithm is a simple (yet somewhat inefficient) algorithm for computing the convex hull of a given set of points. It has O(NK) complexity, where N is the number of points and K is the number of points on the convex hull.

The gift wrapping algorithm begins with a point A known to be on the convex hull (such as the leftmost point) and selects the point B such that all points are to the left (or right) of the line AB. Repeating with B and so on until one reaches A again yields the convex hull. The gift wrapping algorithm is exactly analogous to the process of winding a string (or wrapping paper) around the set of points.

The approach is extendable to higher dimensions.

See also

• Graham scan - more complex algorithm, but more efficient

This article is a stub. You can help Wikipedia by fixing it.