Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

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 Goodman's chapter on "Pseudoline Arrangements" in the Handbook of Discrete and Computational Geometry (CRC Press, 2004); that link takes you to Google books. They are also mentioned in the Wikipedia article on arrangements, but a separate article on pseudoline arrangements is yet to be written.

share|improve this answer
1  
As I understand, the homotopy type of the set of arrangements of lines in $\mathbb R^2$ can be that of any real algebraic variety. In particular, it need not be connected, which in a certain sense says you can't reconstruct the arrangement from these order types. I'm having trouble finding the correct reference, though --- but perhaps Joseph or someone else can fill it in. –  Bill Thurston Dec 30 '10 at 15:30
    
@Bill: Perhaps Mnev's Universality Theorem? en.wikipedia.org/wiki/Mnev%27s_universality_theorem . Here is one statement: If $V$ is a basic semialgebraic set defined over $\mathbb{Q}$, there is a configuration of points in the plane such that the space of all configurations of the same order type as the points is stably equivalent to $V$. (Here I am relying on the same Goodman chapter cited above.) –  Joseph O'Rourke Dec 30 '10 at 18:15
    
These are great comments and answers BUT isn't the question of the OP when can a list of n circular permutations (each omitting one of n symbols) be realized by an arrangement of points (or if I understand your remark, by an arrangement of n actual lines)? Or am I missing something? –  Aaron Meyerowitz Dec 31 '10 at 6:53
add comment

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 Cartheodory's Theorem.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.