Convex Hull

§ Statement

§ Solution

First we pick a reference point $Q_0$, in Graham's scan we pick the $P_i$ with the smallest $y$ coordinate, then the smallest $x$ coordinate in case of a tie.

Then, we can treat each $P_i \in \mathcal{P}$ as a vector starting at the origin, and compute its angle $\theta$ with respect to $Q_0$.

$$\begin{align*} \theta_i &= \arccos \left[\frac{P_i \cdot Q_0}{\|P_i\| \|Q_0\|}\right]. \end{align*}$$

We need not compute the actual angle $\theta$; any function which is monotonically increasing over $[0, \pi]$. Incidentally, the cosine of the angle satisfies this property, hence we can let $\theta = \hat{P}_i\cdot\hat{Q}_0$.

Let $\mathrm{Conv}(P)$ be the empty set, and $Q$ be the set $\mathcal{P}$ ordered by $\theta_i$, let ties be sorted by the $L_2$ from the centroid of $\mathcal{P}.$

Next, we can iterate through each point $Q_i$ of $\mathcal{Q}$.

In each iteration:

• If $\mathrm{Conv}(\mathcal{P})$ has fewer than two points, then
  • insert $Q_i$ to the end of the array and skip to next iteration.
• Check if the triangle formed by $Q_i$ and the last two points of $\mathrm{Conv}(\mathcal{P})$ has positive area (i.e. points turn in anticlockwise direction)
  • If so, add $Q_i$ to the end of $\mathrm{Conv}(\mathcal{P})$.
  • Otherwise, remove the last element of $\mathrm{Conv}(\mathcal{P})$, and repeat above step until $Q_i$ can be inserted.

Finally, return $\mathrm{Conv}(\mathcal{P})$ which is the set containing the points of the convex hull.

§ Algorithm