Date: Wed, 18 Sep 1996 16:49:03

From: David Eppstein

Here's a problem to go with your page

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

64862612 |