2
$\begingroup$

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,

enter image description here

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.