[Solved]: Why are the two farthest points vertices of the Convex Hull?

Problem Detail: 

I read that in a 2D space, the two points farthest away must be in the convex hull (CH).

Intuitively, I can see why. If the two farthest points are not in the convex hull, then there must be a point that is outside the convex hull (contradiction). I know that a vertex of CH has two adjacent edges that converge at that point, which is of further distance from any other vertex or point within CH, than the non-vertices beside it. What I mean is shown in the image below: a vertex (p) with two adjacent edges,

Problem is, I don't see how I can prove this more formally. I am looking for a more concrete proof.

Thank you in advance.

Asked By : Curious

Answered By : Yuval Filmus

Let $p,q$ be two points in your set of points. The point $p$ can be represented as some convex combination $\sum_i \alpha_i p_i$ of points on the convex hull. The triangle inequality gives $$ \|p - q\| = \left\| \sum_i \alpha_i (p_i - q) \right\| \leq \sum_i \alpha_i \|p_i - q\| \leq \max_i \|p_i - q\|, $$ where both inequalities used $\alpha_i \geq 0$ and the second also $\sum_i \alpha_i = 1$. We conclude that $p$ can be replaced by some point on the convex hull. Similarly, having replaced $p$ by a point on the convex hull, we can replace $q$ by a point on the convex hull.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23646