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

## Algorithm Jarvis March

- First, a base point
pis selected, this is the point with the minimum y-coordinate._{o}

- Select leftmost point in case of tie.
- The next convex hull vertices
p_{1}has the least polar angle w.r.t. the positive horizontal ray fromp._{o}

- Measure in counterclockwise direction.
- If tie, choose the farthest such point.
- Vertices
p_{2},p_{3}, . . . ,pare picked similarly until yk = ymax_{k}

p_{i+1}has least polar angle w.r.t. positive ray fromp._{o}- If tie, choose the farthest such point.

- The sequence
*p*,_{o}*p*_{1}, . . . ,*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*in same fashion until obtain_{t}*p*=_{t}*p*._{o}

- Choose pk+1 as the point with least polar angle w.r.t. the negative ray from

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.