Take the 2-minute tour ×
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.

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.

share|improve this question
    
Note that formal proof must be preceded by formal definitions, so a key step would be defining "convex hull of $P$". Most authors take the meaning to be that of convex closure, while you seem to mean something closer to a notion of extremal points of $P$. (I would actually side with you as to a preferred meaning...) –  hardmath Mar 1 at 12:01
    
@hardmath I think the two definitions should be equivalent. In the text I'm looking at, a convex hull is formally defined as "the intersection of all convex sets that contain $P$". A convex set $S$ is defined as usual, $\forall{p,q\in S}(\bar{pq}\subset S)$, where $\bar{pq}$ is the line segment between $p$ and $q$. –  MGA Mar 1 at 12:04
    
Okay, let's take that (the convex closure) to be the definition (which is not the same as the vertices of a polygon). Either the proposition is obviously false (a finite set $P$ will not have its convex closure be finite if not all points in $P$ are collinear) or the word "corresponds" does not mean what I think it does. –  hardmath Mar 1 at 12:09
    
Also if you want another problem which seems to be obvious, but it's not obvious at all how to prove it, consider a square grid on a rectangle and 2 paths in the grid connecting the opposite sides of the rectangle (each different sides of course). Prove that they intersect! –  user2345215 Mar 1 at 12:11
add comment

3 Answers 3

up vote 3 down vote accepted

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$.
share|improve this answer
1  
Similarly, it's "blatantly obvious" that a convex solid with finite volume must have finite surface area, but thinking of the nonconvex Gabriel's horn might persuade a Reader that this isn't necessarily easy to prove. –  hardmath Mar 1 at 12:21
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
I think I catch the drift of your Remark, but instead of directly answering, you've asked three questions in four sentences. –  hardmath Mar 1 at 12:12
1  
@hardmath Well, I just wanted to give general hints on how to start. I could go more into the detail if OP wants. –  user2345215 Mar 1 at 12:14
    
@user2345215 Thank you for your answer. I was also thinking along these lines, but I think what I find hard is actually the next step, i.e. answering the kind of questions you asked. If possible, I would love to see one complete example of how it is done. –  MGA Mar 1 at 12:35
    
@MGA: Ok, it's gonna be hard without pictures (I would make crappy ones), but I'll try to describe it in detail :) –  user2345215 Mar 1 at 12:46
    
@user2345215 Thank you very much for your effort. I guess I can infer the pictures from the context, so don't bother. I'll ask you if I don't get something. :-) –  MGA Mar 1 at 12:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.