Erdős-Szekeres empty pseudoconvex $k$-gons

Question

I am wondering if the Erdős-Szekeres empty convex $k$-gon question has a different answer if convexity is replaced by a pseudoline-version of convexity.

The empty convex $k$-gon question is a variant on the Happy Ending Problem. The last remaining case, $k=6$, was settled about four years ago. It is now known that, although there arbitarily large point sets in the plane with no empty convex heptagon, every sufficiently large set contains an empty convex hexagon.

Here is my attempt to generalize this to pseudolines. An arrangement of pseudolines is a collection of curves each pair of which intersects in exactly one point, at which they cross. There are nonstretchable pseudoline arrangements, i.e., those not combinatorially equivalent to any straight-line arrangement. Here's one:

---

        
         _{(Image by David Eppstein)}

---

In fact, there are many more pseudoline arrangements— $2^{\Omega(n^2)}$, than straight-line arrangements— $2^{O(n \log n)}$, for $n$ lines and simple arrangements.

All the above are facts. Caveat: my attempt at defining convexity in this context might not make sense. Given $n$ points in the plane, say that they contain an empty pseudoconvex $k$-gon if

1. there is an arrangement $\cal{A}$ of $\binom{n}{2}$ pseudolines through the $n$ points.
2. there is an empty $k$-gon $K$, a region of the plane bounded by $k$ pseudolines containing no points in its interior.
3. $K$ is convex in the sense that for any two additional points $a,b$ inside $K$, one can find a pseudoline through $a,b$ compatible with the arrangement $\cal{A}$, such that the pseudosegment $ab \subset K$.

Assuming this definition is not inconsistent, does the Erdős-Szekeres empty convex $k$-gon question have a different answer? For example, perhaps every sufficiently large point set always has a pseudoconvex heptagon?

Aside from this question, I would be interested in learning of convexity definitions analogous to what I tried to define above. Thanks for pointers/ideas!

Answer 1

(Long comment, not an answer to the question posed.)

One way to generalise "general position" configurations of lines in the plane is to assign an orientation "clockwise" or "anticlockwise" to each set of three points and require a small set of axioms to hold. These purely combinatorial objects were called CC systems by Don Knuth in his book "Axioms and Hulls". In the book he proves a correspondence with geometric configurations of pseudolines. There is also a combinatorial definition of "convex polygon" and "interior", so the problem can be stated in a purely combinatorial form. I suggest you check that out as it will probably match your intuition.

Note that the original happy ending problem for 17 points, proved by Peters and Szekeres by computer, also holds for CC systems using much the same computation.