Update #2: Mostly about lower-bound arrangements

The problem: What's the most points you can place and avoid making a convex n-gon?

The conjecture is that 2^(n-2)+1 points force an n-gon (so 2^(n-2) is the max points you can place without one)

An arrangement is "n-primal" if it contains no convex n-gon, but forces a convex n-gon no matter where the next point is placed.

First, a 4-primal arrangement with 4 points, and a 5-primal arrangment with 8 points:












It's easy to see that you can always put an (n-1)-gon inside another and have it remain safe. That gives a not-very-tight lower bound of g(n) >= 2(n-1). Even though the right-hand arrangement is 5-primal, we'd also need to prove that all arrangements with 8 points are also 5-primal (or already have the 5-gon) to show that 8 is the maximum number of points for n=5

A lot of messing about made me suspect that every n-primal arrangement has the same number of points in it. In other words, you can keep placing points, and regardless of how you decide to place them, you can't make a "mistake"--you won't be forced to create an n-gon until you've placed as many points as you can.

Proving this would have been helpful as it it would mean that finding one example of an n-primal arrangement would prove the conjecture for that n. Unfortunately, I think this is a counter-example to the claim: a 5-primal arrangement with only 7, instead of 8 points. Bummer.

To the right is an arrangement with 16 points and no 6-gons--I also believe it to be primal (though haven't really proven it).

Here's how we thought about it. Ignoring the center point, it contains 5 "regions" with 3 points each. The shape was constructed so that you can't select 6 points without forcing them to be concave. (Alternatively, if you're selecting points such that they remain convex, you can select at maximum 5).

Since we need 6 points for a 6-gon and there are only 5 regions, we need at least two points from at least one region. For example, 2 points in one region, and 1 point from the other 4 regions would work. So would 2 points from 2 regions, and 1 point from the remaining two; or 3 points from one region and 1 point from 3 other regions, etc.

Start at any point and attempt to construct a convex 6-gon by only turning either only counter-clockwise or only clockwise (I'll consider counter-clockwise here). The arrangment is constructed so that whenever you include 2 points in the same region, you're forced to "skip" the next region in order to keep the polygon you're building convex. That means that if you include 2 points from one region, you can only include 1 point from 3 other regions, instead of 4, which only gives you a convex polygon with 5 points total--not 6, as needed. If you include 2 points from 2 regions, you can only include 1 point from 1 other region and have it remain convex. Similarly, if you include 3 points in the same region, you're forced to skip 2 regions to remain convex. If you play around, you'll see that all the ways of making the convex 6-gon by selecting points from regions have been prevented.

The center point doesn't alter any of this. You can think of it as an extra region you could choose to visit, except it can only contain 1 point. Whenever you choose it, you're forced to skip at least one region, which means that it will never let you gain more points than you could have without it.
It seems as if this sort of approach can be generalized. For example, we could put 5 points in each of 6 regions such that selecting 2 points forces you to skip 1 region, 3 points to skip 2 regions, 4 points to skip 3 regions, etc. In general, we might make (n-1)-regions oriented roughly as the verticies of a convex (n-1)-gon might be. Each region contains a "cup" shape with (n-2) points in it arranged as I've described above.

This is an interesting idea, but still doesn't get us close to the conjecture number and leaves other questions. Arrangements with this form would grow as g(n) = (n-1)*(n-2) + c, which still isn't anywhere close to 2^(n-2). There are still ideas to explore, though:

What if we arranged the regions differently? For example, since the regions can be thought of as akin to points, should the regions be arranged in "primal" arrangements themselves? This sort of recursive embedding would certainly get the points growing fast enough to be exponential.

Anyhow, those were some experiments we've run lately. I'll keep everyone updated as we discover more!

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.

Happy ending problem

Ok! To innagurate my new "blog", here's a math problem I've been working on recently (really a lot more since school got out).

The problem is:

What's the greatest number of points you can put on a plane (with no 3 in a line) until you can be certain some subset of them make the verticies of a convex n-gon (for some n).

The guy who gave me this problem had found that certain Ramsey numbers were an upper bound, but that's not much help since we didn't think they were a very tight upper bound, and no one knows how to calculate them anyhow.

With a little research, we discovered that this is actually a well-known problem which you can read a bit more about here:
http://mathworld.wolfram.com/HappyEndProblem.html

It's bounded both above and below. There's a conjecture that the max points (I'll call it g(n)) is given by: g(n) = 2^(n-2)+1.

I was going to report some of our thoughts (they don't really count as "progress"), but it occured to me it would be much easier with pictures which I'm too busy to make right now.

The good news is that I'm almost done with some Mathematica functions that will extend the cases we can visualize and explore--so maybe when I'm done with that I'll post an update and some pictures.

In the meantime, insights are welcome!