View source for Gift wrapping algorithm

{{short description|Algorithm for computing convex hulls in a set of points}}
[[File:Animation depicting the gift wrapping algorithm.gif|thumb|Animation of the gift wrapping algorithm. The red lines are already placed lines, the Black line is the current best guess for the new line, and the green line is the next guess]]

In [[Computational geometry|computational geometry]], the '''gift wrapping algorithm''' is an [[Algorithm|algorithm]] for computing the [[Convex hull|convex hull]] of a given set of points.

==Planar case==
In the two-dimensional case the algorithm is also known as '''Jarvis march''', after R. A. Jarvis, who published it in 1973; it has [[Big O notation|O]](''nh'') [[Time complexity|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{{citation needed|date=March 2018}}. In general cases, the algorithm is outperformed by many others ( See [[Convex hull algorithms]]).

==Algorithm==
For the sake of simplicity, the description below assumes that the points are in [[General position|general position]], i.e., no three points are collinear. The algorithm may be easily modified to deal with collinearity, including the choice whether it should report only  [[Extreme point|extreme point]]s (vertices of the convex hull) or all points that lie on the convex hull{{citation needed|reason=Link to a resource describing the details for these degenerate cases required.|date=March 2018}}. Also, the complete implementation must deal{{how|date=March 2018}} with degenerate cases when the convex hull has only 1 or 2 vertices, as well as with the issues of limited arithmetic precision, both of computer computations and input data.
 
The gift wrapping algorithm begins with ''i''=0 and a point ''p<sub>0</sub>'' known to be on the convex hull, e.g., the leftmost point, and selects the point ''p<sub>i+1</sub>'' such that all points are to the right of the line ''p<sub>i</sub> p<sub>i+1</sub>''. This point may be found in ''O''(''n'') time by comparing [[Polar coordinate system|polar angle]]s of all points with respect to point ''p<sub>i</sub>'' taken for the center of polar coordinates. Letting ''i''=''i''+1, and repeating with until one reaches ''p<sub>h</sub>''=''p<sub>0</sub>'' again yields the convex hull in ''h'' steps.  In two dimensions, the gift wrapping algorithm is similar to the process of winding a string (or wrapping paper) around the set of points.

The approach can be extended to higher dimensions.

==Pseudocode==
[[File:Jarvis march convex hull algorithm diagram.svg|thumb|280px|right|Jarvis's march computing the convex hull.]]

 '''algorithm''' jarvis(S) '''is'''
     // ''S'' is the set of points
     // ''P'' will be the set of points which form the convex hull. Final set size is i.
     pointOnHull = leftmost point in S // which is guaranteed to be part of the CH(S)
     i := 0
     '''repeat'''
         P[i] := pointOnHull
         endpoint := S[0]      // initial endpoint for a candidate edge on the hull
         '''for''' j from 0 to |S| '''do'''
             // endpoint == pointOnHull is a rare case and can happen only when j == 1 and a better endpoint has not yet been set for the loop
             '''if''' (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint) '''then'''
                 endpoint := S[j]   // found greater left turn, update endpoint
         i := i + 1
         pointOnHull = endpoint
     '''until''' endpoint = P[0]      // wrapped around to first hull point

==Complexity==
The inner loop checks every point in the set ''S'', and the outer loop repeats for each point on the hull.  Hence the total run time is <math>O(nh)</math>.  The run time depends on the size of the output, so Jarvis's march is an [[Output-sensitive algorithm|output-sensitive algorithm]].

However, because the running time depends linearly on the number of hull vertices, it is only faster than  <math>O(n \log n)</math> algorithms such as [[Graham scan]] when the number ''h'' of hull vertices is smaller than log&nbsp;''n''. [[Chan's algorithm]], another convex hull algorithm, combines the logarithmic dependence of Graham scan with the output sensitivity of the gift wrapping algorithm, achieving an asymptotic running time  <math>O(n \log h)</math>  that improves on both Graham scan and gift wrapping.

==See also==
* [[Convex hull algorithms]]

==References==
{{refbegin}}
* {{Introduction to Algorithms|2|chapter=33.3: Finding the convex hull|pages= 955&ndash;956}}
*{{cite journal
 | author = Jarvis, R. A.
 | title = On the identification of the convex hull of a finite set of points in the plane
 | journal = [[Information Processing Letters]]
 | volume = 2
 | year = 1973
 | pages = 18–21
 | doi = 10.1016/0020-0190(73)90020-3}}
{{refend}}

[[Category:Polytopes]]
[[Category:Convex hull algorithms]]

{{Sourceattribution|Gift wrapping algorithm}}