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.
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.