User solid snake - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T20:58:51Z http://mathoverflow.net/feeds/user/11907 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50705/arrangements-of-points-in-the-plane Arrangements of points in the plane Solid Snake 2010-12-30T07:19:19Z 2010-12-30T13:21:46Z <p>Let $p_1,\ldots,p_n$ be a collection of distinct points in $\mathbb{R}^2$, no three of which lie on a line. For each $p_i$, let $\omega_i(p_1,\ldots,p_n)$ be the following ordered list (well-defined up to cyclic permutation). Choose some direction $\theta$ such that none of the $p_j$ lie on the ray from $p_i$ going in the direction $\theta$. Rotate $\theta$ clockwise in a full circle, and record the ordered list of the $p_j$ you encounter. The result is $\omega_i(p_1,\ldots,p_n)$.</p> <p>The ordered lists of points $\omega_i(p_1,\ldots,p_n)$ thus encode some of the combinatorics of how the $p_i$ lie in the plane.</p> <p>My question is under what circumstances can you go in the other direction? More precisely, assume that you are given $n$ ordered lists $\sigma_1,\ldots,\sigma_n$, where $\sigma_i$ contains exactly the elements of <code>$\{p_1,\ldots,p_n\} \setminus \{p_i\}$</code> with no repetitions and is well-defined up to cyclic permutations. When can you find points $p_1,\ldots,p_n$ in $\mathbb{R}^2$ such that $\omega_i(p_1,\ldots,p_n) = \sigma_i$ for all $i$?</p> <p>It is trivial that for $i=1,2,3$, this can always be achieved. However, for $i=4$ it is not hard to find $\sigma_i$ as above that can not be realized. Alas, it is hard to find any general patterns.</p> <p>Here is a slightly less vague question/guess as to what might be true. I wonder if there might be some kind of "local condition" of the following form. There exists some $N$ such that if $\sigma_1,\ldots,\sigma_n$ is a collection of lists as above, then there exists points $p_1,\ldots,p_n$ as above if and only if for every $m$ element subset $S$ of <code>$\{p_1,\ldots,p_n\}$</code> with $m \leq N$, the lists obtained from the $\sigma_i$ by deleting the points not in $S$ and throwing away the corresponding lists can be realized?</p>