Erdős-Szekeres empty pseudoconvex $k$-gons - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T06:55:41Z http://mathoverflow.net/feeds/question/88480 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88480/erds-szekeres-empty-pseudoconvex-k-gons Erdős-Szekeres empty pseudoconvex $k$-gons Joseph O'Rourke 2012-02-15T01:56:39Z 2012-02-15T01:56:39Z <p>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.</p> <p>The empty convex $k$-gon question is a variant on the <a href="http://en.wikipedia.org/wiki/Happy_ending_problem#Empty_polygons" rel="nofollow">Happy Ending Problem</a>. 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.</p> <p>Here is my attempt to generalize this to pseudolines. An <em><a href="http://en.wikipedia.org/wiki/Arrangement_of_lines#Other_types_of_arrangement" rel="nofollow">arrangement of pseudolines</a></em> is a collection of curves each pair of which intersects in exactly one point, at which they cross. There are <em>nonstretchable</em> pseudoline arrangements, i.e., those not combinatorially equivalent to any straight-line arrangement. Here's one: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/P8.jpg" alt="Nonstretchable" /> <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <sub><a href="http://11011110.livejournal.com/15749.html" rel="nofollow">(Image by David Eppstein)</a></sub> <br /> In fact, there are many more pseudoline arrangements&mdash; $2^{\Omega(n^2)}$, than straight-line arrangements&mdash; $2^{O(n \log n)}$, for $n$ lines and simple arrangements.</p> <p>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 <em>pseudoconvex</em> $k$-gon if</p> <ol><li> there is an arrangement $\cal{A}$ of $\binom{n}{2}$ pseudolines through the $n$ points.</li> <li> there is an empty $k$-gon $K$, a region of the plane bounded by $k$ pseudolines containing no points in its interior.</li> <li> $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$.</li></ol> <p>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?</p> <p>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!</p>