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
    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?2012-07-17
  • 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.2012-07-17
  • 1
    Shahab, consider triangulating the convex hull.2012-07-17
  • 0
    You need to find four points for a quadrilateral, including the one which causes the problem.2012-07-17
  • 0
    @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.2012-07-17
  • 0
    Is this a formal proof: We divide the convex hull into triangles. There is bound to be a point P in the interior of any triangle. Joining any two points of the triangle with P gives a non-convex quadrilateral. I am not clear how to rigorously prove the first aand last sentence.2012-07-17
  • 0
    As WimC points out, there may be a point $P$ in the interior of some triangle, or maybe all you get is $P$ on the boundary of a triangle. If there is a point $P$ in the interior of, say, the triangle $ABC$, then the four points $A,B,C,P$ form a non-convex quadrilateral. If $P$ is on the boundary of $ABC$ then you really have to think about the example WimC raises.2012-07-18
  • 0
    In a non-formal way I think that if P is on the boundary of ABC and A,B,C are vertices among n then PABC is not a quadrilateral at all, its convexity aside. The hypothesis states that any four must form a quadrilateral. (No 3 points among n are collinear).2012-07-18
  • 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.