3
$\begingroup$

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

$\endgroup$

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.