Why are the two farthest points vertices of the Convex Hull?

Question

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.

Answer 1

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.

Answer 2

Actually, the farthest point in any direction is on the convex hull. Actually, this applies much more generally. (I think probably for any closed and bounded set, but my real analysis is a little rusty.) Let $P$ be a simple closed polygon in the plane. Then $P$ partitions the plane into 3 regions: the interior of $I$ of $P$, the exterior $E$ of $P$, and the boundary $P$ itself. (Bonus reading: see the the Jordan Curve Theorem.) Without loss of generality, we assume that the direction is the positive $x$ axis (just rotate your coordinate system).

Let $p$ be a point in $I \cup P$. If $p$ is not on the boundary $P$, then there exists another point $q$ in $I \cup P$ near $p$ with a larger $x$ coordinate, and so $p$ is not the point in $I \cup P$ with maximum $x$ coordinate. The contrapositive is that the point in $I \cup P$ with maximum $x$ coordinate is on the boundary $P$.

Answer 3

I'm late for the party, but anyway... Let $p$ and $q$ be two points, such that the distance $d$ between them is maximum over all the pairs of points in the given point set. All the other points must be inside the intersection of two disks with radius $d$ - one disk with center in the point $p$ and another disk with center in the point $q$. This intersection looks like a curvilinear rhombus with diagonal $(p, q)$ and circular sides with radius $d$. Now we'll use the observation from the @Joe answer - the farthest point in any direction belongs to the convex hull. In our case this direction is defined by the line, passing through points $p$ and $q$, and these two points are obviously farthest along this direction.