Search code examples
algorithmgraphconvex-hull

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


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.


Solution

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