# Thread: Proof verification: Smallest Perimeter convex polygon

1. ## Proof verification: Smallest Perimeter convex polygon

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

Show that the smallest perimeter polygon containing a set of points is convex.

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.

2. ## Re: Proof verification: Smallest Perimeter convex polygon

Originally Posted by mdm508
Show that the smallest perimeter polygon containing a set of points is convex.
This is an totally non-sense question. Do you even know what a polygon is?
What set of points are you dealing with? It must be co-planar points. But then are you considering the polygon to be its boundary union its interior? OR WHAT?

In other words, it appears that you have no idea of the definitions of that you are using.
What if the set is a collection of colinear points? What polygon makes any sense to say contains that set?

3. ## Re: Proof verification: Smallest Perimeter convex polygon

I just copy and pasted the question from book. I know what a polygon is. Just assume that no points in the set are collinear. Assume it is just some set of points. Basically we are trying to show that the smallest perimeter polygon of a set of points is the Convex Hull.

4. ## Re: Proof verification: Smallest Perimeter convex polygon

Originally Posted by mdm508
I just copy and pasted the question from book. I know what a polygon is. Just assume that no points in the set are collinear. Assume it is just some set of points. Basically we are trying to show that the smallest perimeter polygon of a set of points is the Convex Hull.
Let this be a lesson: always give us ALL the information.
You should have access to a mathematics library. This problem is discussed on page 75 of Roberts&Varberg. Read their explanation. then if you have questions, post them.