# $n$ points forming a convex $n$-gon

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.

-

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?

-
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
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
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
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.