Arrangements of points in the plane

Question

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)$.

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.

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 $\{p_1,\ldots,p_n\} \setminus \{p_i\}$ 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$?

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.

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 $\{p_1,\ldots,p_n\}$ 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?

Answer 1

Goodman and Pollack called sequences that encapsulate the combinatorics of an arrangement of lines allowable sequences in their classic paper "Semispaces of Configurations, Cell Complexes of Arrangements" (J. Combin. Theory Ser. A, 37:257-293, 1984.) These sequences are equivalent, I believe, to your sequences. (One of GP's theorems is that a sequence of permutations is realizable by points iff it is realizable by lines.) They established the following theorem concerning allowable sequences:

Every allowable sequence of permutations can be realized by an arrangement of pseudolines.

Pseudolines are curves each pair of which intersect exactly once. (More precisely, a pseudoline is a simple closed curve that does not disconnect $\mathbb{P}^2$.) So I think the answer to your question is that the sequences determine pseudoline arrangements, which correspond to "generalized configuration of points," rather than line arrangements, which correspond to configurations of points. Most pseudoline arrangements are not stretchable, i.e., they do not correspond to a line arrangement. So you cannot, in general, reconstruct the point configuration from the sequence. (However, every arrangement of $\le 8$ pseudolines is stretchable, so your efforts can be extended to $i=8$.) There is some work on local conditions with which I am not familar: Felsner and Weil, "Sweeps, Arrangements and Signotopes" (Discrete Applied Math 109:257-267, 2001). Perhaps this is related to your local conditions.

There remains no characterization of stretchability. Peter Shor showed that determining if a pseudoline arrangement is stretchable is NP-hard ("Stretchability of pseudoline arrangements is NP-hard," in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, 1991). This certainly accords with your "Alas, it is hard"!

Another source on this topic is Felsner & Goodman's chapter on "Pseudoline Arrangements" in the Handbook of Discrete and Computational Geometry (CRC Press, 3rd Ed., 2017). Here's a near-final PDF of that chapter: Pseudoline Arrangements. They are also mentioned in the Wikipedia article on arrangements, but a separate article on pseudoline arrangements is yet to be written.

Answer 2

That's a nice question and I like your conjectured possible form of a local condition. It reminds me of various theorems about convex sets such as Helly's Theorem. I think I can see that an ordered list of points are the vertices of a convex polygon (in clockwise order) exactly if your lists restricted to those points are the same list with a deletion. Given such a convex polygon we can also tell which points are inside it and which outside. I'd guess that $N=4$ is enough. Also that if one knows the lists for every $4$ point set then one can reconstruct all the convex polygons. That would seem to follow from Carthéodory's Theorem.