# Graham Scan - Why does the first and last points always belong to the convex hull?

Context

In a 2-dimensional space, suppose $p_0$ is the origin - the lowest point of the Convex Hull (CH), and suppose $p_1, ..., p_{n-1}$ are sorted by their polar angles. When applying Graham scam, I always observe that $p_1$ and $p_{n-1}$ are vertices of the Convex Hull (CH). For instance, consider the graph, for which $p_{n-1}$ is $p_{12}$.

Question

How can I show this formally, that $p_{n-1} \in CH$ and $p_1 \in CH$ for all instances?

• $p_1 \in CH$ because $\angle p_{n-1}p_0p_1$ must be a left turn, since $p_0$ is the lowest point and $p_1$ has the smallest polar angle above $p_0$; similarly,

• $p_{n-1} \in CH$ because $\angle p_{n-2}p_{n-1}p_{0}$ must be a left turn, since $p_0$ is the lowest point and $p_{n-1}$ has the largest polar angle above $p_0$.

Does this sound like a convincing proof?

• What you want to show is that the entire point set lies on one side of the line $p_0p_1$ and also to one side of $p_{n-1}p_0$. Your argument basically does this, so you are on the right track. – Louis Mar 27 '14 at 18:41
• Thanks, can you elaborate on the "entire point set lying on one side?" – Curious Mar 30 '14 at 13:52
• In general, $p_ip_j$ is an edge of the convex hull iff the line supporting that segment defines a half-space containing the whole point set. (This is what is witnessed by $p_ip_jp_k$ being a left turn for every $k$.) – Louis Mar 31 '14 at 9:34