1
$\begingroup$

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.

2 Answers 2

3

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?

  • 0
    Shahab, then I think we're done. If the points don't form a convex $n$-gon, then look at the convex hull, and triangulate it. There must be a point not a vertex of the convex hull, it can't be on any of the lines connecting two other points (no 3 collinear), it can't be interior to a triangle (or it would form a non-convex quad with those three points), contradiction. – 2012-07-18
1

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.