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


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

My answer

  • $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?

Thank you in advance.

  • 1
    $\begingroup$ 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. $\endgroup$ – Louis Mar 27 '14 at 18:41
  • $\begingroup$ Thanks, can you elaborate on the "entire point set lying on one side?" $\endgroup$ – Curious Mar 30 '14 at 13:52
  • 1
    $\begingroup$ 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$.) $\endgroup$ – Louis Mar 31 '14 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.