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
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
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$. |
|||
|
|
