I have formulated a proof but was wondering if someone could verify that it is correct.

A concave polygon is clearly not the shortest perimeter polygon that can be formed from a set of points. This can be seen by noting that if there are two line segments that form a reflex angle, then the there exists a shorter path between the end points of the two line segments. This intuition can be used in our proof.

Assume $P$ is the smallest perimeter polygon of a set of points and that $P$ is non-convex (concave). If $P$ is concave this implies there is at least one reflex angle formed between two line segments. Suppose $\overline{PQ},\overline{QR}$ form a reflex angle. Now imagine we add a line segment $\overline{PR}$ to $P$ giving us triangle $PQR$. By the triangle inequality we know that $Length(\overline{PR}) < Length(\overline{PQ} + \overline{QR})$ which implies that there exists a shorter way to get between $P$ and $R$ then in our origianl polygon, which contradicts the assumption that $P$ is the smallest perimeter polygon. This means that $P$ must be convex.

enter image description here


Your Answer

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

Browse other questions tagged or ask your own question.