# Convex hull has the smallest perimeter

How do you show that the convex hull of a given set of points S, always has the minimum perimeter ? By perimeter i mean the length of the boundary of the hull

• Minimum with respect to what? To all convex sets containing S? Cause if its w.r.t. all sets containing S, then it is not true. Take for instance the 4 corners of a square. obviously, the square is the convex hull, its boundary has length $4Z$, $Z$ being the length of one side. But the set of corner points itself has zero length. – Raskolnikov Dec 5 '10 at 21:34
• I mean that the hull has the shortest perimeter of all simple polygons that include every point of S. – user4444 Dec 5 '10 at 21:50

Take an arbitrary simple polygon $\pi$ including every point of $S$, and take some segment $PQ$ of the convex hull. Extend it into a line $\ell$. Form a new polygon $\pi'$ by locating the "left"most and "right"most intersection points $L,R$ of $\ell$ with $\pi$, adding new vertices to $\pi$ at $L,R$, and replacing the part of $\pi$ between $L$ and $R$ by the single line segment $LR$. The resulting polygon $\pi'$ is a simple polygon including all points of $S$, and the triangle inequality implies that its perimeter is smaller or equal to the perimeter of $\pi$.