A Problem of disjoint convex quadrilaterals

Subject: Re: disjoint convex quadrilaterals
Date: Wed, 18 Sep 1996 16:49:03
From: David Eppstein

Here's a problem to go with your page

https://www.cut-the-knot.com/Generalization/points.shtml

which states the problem

        There are 3n points in the plane no three of which lie on the
        same straight line. Is it possible to form n triangles with
        vertices at these points so that the triangles have no points in
        common?

You then go on to generalize the problem to quadrilaterals, not necessarily convex. What about convex quadrilaterals? How many non-colinear points do you need in order to guarantee that you can find n disjoint convex quadrilaterals?

The answer is at least 4n+1 and at most 5n...

David Eppstein

71535312