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.

Suppose I am given a collection of $n$ points, any four of which form a convex quadrilateral. I wish to establish that these $n$ points form a convex $n$-gon.

I am thinking about using induction. The case $n=4$ is trivial. If the result is assumed for $n-1$ how do I establish it for $n$?

Thanks.

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

Consider the convex hull. If it has fewer than $n$ points, then there's a point in its interior. Use that point to form a non-convex quadrilateral - do you see a way to do this?

share|improve this answer
    
Do I pick 2 adjacent extreme points, adjoin them to the interior point and take any fourth point? How do I formally prove that the resulting quadrilateral is non-convex? –  Shahab Jul 17 '12 at 13:10
1  
Be careful with terminology. Consider for example the four vertices of a square together with its centroid. Does this configuration of five points contain a "non-convex quadrilateral"? Also "interior" is too strict. –  WimC Jul 17 '12 at 13:16
1  
Shahab, consider triangulating the convex hull. –  Gerry Myerson Jul 17 '12 at 13:26
    
You need to find four points for a quadrilateral, including the one which causes the problem. –  Mark Bennet Jul 17 '12 at 13:41
    
@WimC Good point - definitions have to be clear. I wonder if AECD is taken to be a triangle (non-quadrilateral), because it is the form of the convex hull which counts. –  Mark Bennet Jul 17 '12 at 13:46
show 4 more comments

Assume that your point set $P$ is non-convex, then there is a point, say $p$, contained in the interior of the convex hull of $P$. By Carathédory's Theorem there is a triple $t_1,t_2,t_3$ of points of $\text{conv}(P)$ such that $p$ lies inside the convex hull of $t_1,t_2,t_3$. Clearly, $p,t_1,t_2,t_3$ forms a non-convex quadrilateral, which contradicts the assumption.

share|improve this answer
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.