Visualizing lower bound for the Happy Ending Problem (small cases).

243 Views Asked by At

I'm studying the Happy Ending Problem now, which states that

For any positive integer $s$, any sufficiently large finite set of points in the plane in general position has a subset of $s$ points that form the vertices of a convex polygon.

Let $g(s)$ denote the minimum number of points in general position whose set must contain a convex $s-$gon. It's known that $g(s) = 2^{s-2}+1$ for $s\le 6$, but the exact value for $s>6$ is unknown. However, it has been shown that $g(s) > 2^{s-2}$ for all $s$ through an example of a set of $2^{s-2}$ points without any convex $s-$gon. I've seen the construction of this example, but I have a hard time visualizing it because it involves organizing sets of points very distant from each other recursively.

I'm looking for a geometric visualization of sets like that for small cases of $s$. It is easy to find the setting for $s = 4$ and $s = 5$ (which are as follows) in the online articles on the subject, but I was unable to find any illustration for $s\ge 6$. An example for the case $s = 7$ would satisfy me a lot.

image

Above, examples for $s=4$ (violet) with $4$ points for and $s=5$ (green) with $8$ points.


Edit: Going with my intuition, I have found the following set of $16$ points which seems to not contain any convex hexagon. There are too many polygons to check, though, despite of all the symmetries, so I'm not sure about it.

enter image description here

In the figure I'm using a polar grid with an angle of $\dfrac{\pi}{40}$, in case someone wants to extract the exact coordinates.

I think those examples for $4\le s\le 6$ (if the last one is correct) consisting of concentric $s$-gons are pretty neat, but my hopes for this pattern to continue are not very high.

1

There are 1 best solutions below

0
On

If you can track down a copy of the paper "On some extremum problems in elementary geometry" by Erdős and Szekeres (Ann. Univ. Sci. Budapest. Eotvos Sect. Math. 3-4 (1961) 53-63.), they describe such a construction of $2^{n-2}$ set that is void of convex $n$-gons. It is also reprinted in "Paul Erdős: the art of counting. Selected writings". Alas, there is no visualization there in the paper but an algorithm to construct such sets. I don't have copies of these on hand, but you may try to find them. Best of luck!

Edit.

If I didn't implement it incorrectly, we have for $n=6$ the following $16$ points in cartesian coordinates without a convex hexagon:

   1      1
   2301   -459
   5305  -1210
   5306  -1208
   5307  -1201
   5308  -1170
   6592  -1639
   6593  -1630
   6594  -1628
   6595  -1567
   6596  -1565
   6597  -1558
   6938  -1812
   6939  -1764
   6940  -1755
   6941  -1753

Which is kind of hard to see from its plot: enter image description here

And for $n=7$ the following $32$ points:

        1        1
    16135    -2688
    63595   -12180
    63596   -12178
    63597   -12171
    63598   -12140
    63599   -11975
    96151   -20319
    96152   -20310
    96153   -20308
    96154   -20247
    96155   -20245
    96156   -20238
    96157   -19499
    96158   -19497
    96159   -19490
    96160   -19459
   109624   -24810
   109625   -24762
   109626   -24753
   109627   -24751
   109628   -23990
   109629   -23981
   109630   -23979
   109631   -23918
   109632   -23916
   109633   -23909
   111766   -25881
   111767   -25581
   111768   -25533
   111769   -25524
   111770   -25522