Update #1: This isn't so much an update, as a basic walk-through of the smallest case to get a feel for the problem (also a chance for us to play with a program we found called C. A. R. which is sort of like a free version of Geometer's Sketchpad and can be downloaded here. You can thank it for all the beautiful pictures!)

The problem, once again, is: How many poins can we put down without any subset of them creating a convex n-gon?

Since no 3 can be in a line, any 3 points we place automatically make a triangle. So the first non-trivial case is for n=4.

Here is a picture of the first 3 points we place, and the triangle they make.

The question is, where can we put a 4th point without making a convex quadrilateral (4-gon).

You'll see that the area inside the triangle is safe, as are the areas emenating from the verticies of the triangle (depicted as green zones in the picture). We've been calling these "safe zones" because putting a 4th point in any of them won't create a convex 4-gon.


The areas depicted in red which lie adjacent to the sides of the triangle we've been calling "danger zones," because any point in those zones will combine with the triangle to produce the convex 4-gon we're trying to avoid (as is shown to the left here).

In general, if we're trying to avoid making a convex n-gon, and we have a convex (n-1)-gon, the same danger and safe zones will exist.

Let's place our 4th point in the middle of the triangle (which is a safe zone). This creates a number of new triangles with their own safe and danger zones. The picture to the right illustrates the safe zones from the original triangle, plus some danger zones from one of the new triangles (which, you note, makes some of the formerly safe zones unsafe now). The question is, where could you put a 5th point and still avoid making the convex 4-gon?

Look at the picture for a bit and try and find an area for yourself.

Eventually, the danger zones of all the triangles will cover the entire plane. When that happens, no matter where you put the next point it will make the 4-gon. We've been calling arrangements with that property "primal" arragements (or "n-primal" since they depend on the n-gon you're trying to avoid).

When you find a primal arrangement, the question is whether it's the largest primal arrangement. However many points are in your primal arrangement, maybe if you'd arranged them differently, a safe zone would open up that could let you put another point down.

In the case of our problem, I hope you discovered that the arrangment above is primal, because the danger zones of triangles cover the whole plane. There's nowhere safe to put a 5th point. The question is: what if we hadn't put the 4th point in the middle of the original triangle? If we'd put it somewhere else, would we be able to put down a 5th point?

As you'll note in the picture to left, when we put the 4th point in one of the other safe zones, it actually recreates the arrangement we investigated above: a triangle with a point inside.

So that's a sketch of a proof that for n=4, g(n)=5 points are guarenteed to contain a convex 4-gon.

Explore n=5 and n=6 a bit, and in the next post I'll post a few thoughts we've had that are a little more general.