Jarvis march computes the CH(Q) by a technique known as gift wrapping or package wrapping.

Algorithm Jarvis March

• First, a base point p_o is selected, this is the point with the minimum y-coordinate.
  • Select leftmost point in case of tie.
• The next convex hull vertices p₁ has the least polar angle w.r.t. the positive horizontal ray from p_o.
  • Measure in counterclockwise direction.
  • If tie, choose the farthest such point.
• Vertices p₂, p₃, . . . , p_k are picked similarly until yk = ymax
  • p_i+1 has least polar angle w.r.t. positive ray from p_o.
  • If tie, choose the farthest such point.

• The sequence p_o, p₁, . . . , p_k is right chain of CH(Q).
• To choose the left chain of CH(Q) start with p_k.
  • Choose pk+1 as the point with least polar angle w.r.t. the negative ray from p_k.
  • Again measure counterclockwise direction.
  • If tie occurs, choose the farthest such point.
  • Continue picking p_k+1, p_k+2, . . . , p_t in same fashion until obtain p_t = p_o.
     

Complexity of Jarvis March

For each vertex p belongs to CH(Q), it takes

• O(1) time to compare polar angles.
• O(n) time to find minimum polar angel.
• O(n) total time.
   

If CH(Q) has h vertices, then running time O(nh). If h = o(lg n) (this is little Oh), then this algorithm is asymptotically faster than the Graham’s scan. If points in set Q are generated by random generator, the we expect h = c lg n for c≈1.
 

In practice, Jarvis march is normally faster than Graham’s scan on most application. Worst case occurs when O(n) points lie on the convex hull i.e., all points lie on the circle.