Jarvis March

 

 

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

 

Algorithm Jarvis March

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

 

 

 

 

 

 

Complexity of Jarvis March

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

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.