Notation

• ${\rm CH(Q)}$ represents convex hull

Graham’s Scan $O(n\lg n)$

It solves convex-hull problem by maintaining a stack $S$ of candidate points. It pushes each point of the input set $Q$ onto the stack one time, and it eventually pops from the stack each point that is not a vertex of ${\rm CH}(Q)$.

• $p_0$ is the point in $Q$ with th eminimum $y$-coordinate (leftmost in case of tie)
• $\langle p_1, p_2,…p_m\rangle$ remaining points in $Q$ sorted by polar angle in counterclockwise order around $p_0$, (take farthest in case of tie.)
• $S=\langle p_0, p_1, p_2\rangle$ (pop from right side, $p_2$ first)
• For point $p_i=p_3$ to $p_m$
  • While angle formed by points second and first element of $S$ make a nonleft turn: Remove top elemnt.
  • push $p_i$ to $S$
• Finally, $S={\rm CH(Q)}$

Jarvis’ March $O(nh)$

[Here $h$ is the number of vertices in ${\rm CH(Q)}$, where $h$ is $o(\lg n)$]

We start from lowest point $p_0$ and take the point with smallest polar angle wrt $p_1$. Then we take $p_2$ with the smallest poisitive angle wrt $p_1$ and so on until we reach the highest point $p_k$, then we do the same but we calculate the angle from negative x-axis. Finally we reach back at $p_0$.