Prove that the farthest point among a set of points(in 2-d plane) should lie on the convex hull

Question

The question speaks for itself. It is required to prove that given a set of 2-d points, the pair of points farthest from each other must lie on the convex hull.

Answer 1

A point A is on the convex hull if there exists a line through it for which all points in your set of points are on the same side of this line. For the two points farthest away from each other in a set, A and B, you can prove that this holds for the lines perpendicular to A and B, through A and B.

Answer 2

Adding few more details to the answer above.

Claim 1: The point(P) with minimum y-coordinate will always lie on the convex hull of a set of N points.

Proof: Let's assume that the point(P) with minimum y-coordinate lies strictly inside the convex hull. Then there would exist a point(Q) on the convex hull such that Qy < Py, thereby contradicting the assumption that that point P has the minimum y-coordinate.

Claim 2: A point A is on the convex hull if and only if there exists a line through it for which all points in the set of points are on the same side of the line.

Proof: (Only if condition) Consider the point P with minimum y coordinate. From Claim 1, point P lies on the convex hull and the line passing through P parallel to x-axis satisfies the criteria that all other points of set S lies above it. Now for any other point(P') on the convex hull, we can rotate the coordinate axis such that P' has the minimum y-coordinate.

(If condition) Let the point P be such that there exists a line(L) for which all points in the set are on one side. Rotate the coordinate axis in way that slope of L becomes zero, thereby making P a point with minimum y-coordinate. Now use Claim 1 to show that it is indeed a point on the convex hull.

The Claim 2 can now be utilized as to prove that the farthest pair would indeed lie on the convex hull as mentioned in the previous answer.