Proving the Obvious

Question

Is it normal that I have the hardest time when I'm trying to prove statements that are blatantly obvious on a visual and/or intuitive level?

For instance, how does one go about formally proving the following statement?

Given a set $P$ of points on the real plane that are not all collinear, prove that there is a subset of $P$ that corresponds to the convex hull of $P$. Furthermore, that this polygon is unique (up to collinear points).

An intuitive 'proof' would be "Stretch a rubber band such that it contains all the points, and release it." This, at least to me, makes it obvious that the above statement is true, but of course it's not very rigorous.

Answer 1

Is it normal that I have the hardest time when I'm trying to prove statements that are blatantly obvious on a visual and/or intuitive level?

Yes, this is quite common.

• The Jordan curve theorem is a classic example of a geometrically obvious theorem that is true, but quite hard to prove.

• The idea that there do not exist space-filling curves is a classic example of a geometrically obvious "theorem" that is in fact false.

Now, you also asked a specific question, namely:

Given a set P of points on the real plane that are not all collinear, prove that there is a subset of P that corresponds to the convex hull of P. Furthermore, that this polygon is unique (up to collinear points).

This is result is quite easy to prove, but only if you know the "trick" (otherwise, you'll have no idea how to even get started). Anyway, to see that every set $P \subseteq \mathbb{R}^2$ has a convex hull:

1. Let $P$ denote a subset of $\mathbb{R}^2$.
2. Let $K$ denote the collection of all convex subsets $Q$ of $\mathbb{R}^2$ with $P \subseteq Q$.
3. Show that the intersection of $K$ is itself convex, and define that this intersection is the convex hull of $P$.

Answer 2

I assume your set P is finite (you are talking about a polygon).

You can start by choosing the rightmost point $P_0$ (the lowest one if there are more) and imagining a vertical line through it. Let's call $r$ the bottom ray of the line starting at $P_0$.

Now choose the point which minimizes the oriented angle (clockwise) between $r$ (the farther one from $P_0$ if there are more) and call it $P_1$. This is well defined because there cannot be only $1$ point.

Now repeat the procedure with the ray $P_0P_1$, you get a point $P_2$ and so on.

There are 2 things to note which are obvious from the construction:

• $P_i\neq P_{i+1}$ for all $i\geq0$.
• All points lie within the angle $|\measuredangle P_iP_{i+1}P_{i+2}|<\pi$ for all $i\geq0$.

There are only finitely many points, so there is a number $n$ such that $P_n=P_k$ for some $k<n$. Choose $n$ to be smallest possible.

So all points lie within the convex polygon $P_kP_{k+1}\dots P_{n-1}$ and it's nondegenerate, because not all points lie on a line segment.

The last thing to note is that a point in a convex polygon is a vertex if and only if there's a line which intersects the polygon just at that point. Using this we get the points are unique and $k=0$, because $P_0$ is a vertex.

Answer 3

To show uniqueness is easy, and not covered by other answers. If you have two distinct convex polygons which contain all your points, then their intersection is also a convex polygon which contains all the points.

The two original polygons cannot both be minimal unless they coincide.

To use your rubber band analogy, assuming $P$ is finite, you could proceed as follows.

First contain your points in a finite square with horizontal and vertical sides. This confines your points in a finite convex set. Note also that a line divides the plane into two half-planes - these half planes are convex, and the intersection of two convex sets is convex.

Now identify the top point of your set (or one of them). Draw a horizontal line through this point, so all the points not on the line are below it. Call the leftmost of the points (perhaps there is only one) $P_1$. Now rotate the line clockwise about $P_1$ until it meets another point (it may meet more than one). This becomes $L_1$ and the point on $L_1$ furthest from $P_1$ we call $P_2$ - if we are facing from $P_1$ to $P_2$ all the points are on our right. We reduce the square by intersecting it with this right half-plane. We then rotate about $P_2$ to find $L_2$ and $P_3$ etc, always keeping all the points on our right and cutting off parts of the original square as we go.

Since we have only a finite number of points, we can't keep going for ever. When the line comes horizontal again, with all the points on the right i.e. below, it must go through $P_1$ otherwise $P_1$ would be above the line.

I think that can be made rigorous.