Configurations from arrangement of lines

Question

Suppose we have an arrangement of $n$ lines in the plane. This partitions the plane into regions. We can label each region by a string in $\{+1, -1\}^n$, where the $i$'th coordinate is +1 if the region lies above the $i$'th line and -1 if it lies below the $i$'th line. (By rotating the arrangement if necessary, we can assume that no line is perfectly vertical.)

Say that a subset $S$ of $\{+1,-1\}^n$ is realizable by a linear arrangement if there exists a linear arrangement such that the labels of the regions are exactly the strings in $S$. Is there previous study of which subsets of $\{+1, -1\}^n$ are realizable by linear arrangements? One can also ask the same question for hyperplane arrangements.

Answer 1

This problem is known as the question of realizability of pseudoline arrangements by straight lines. An arrangement of pseudolines is an arrangement of $n$ curves in the plane, such that any two curves intersect exactly once. For pseudolines, you can define the same labeling as the OP does. Pseudoline arrangements are related to oriented matroids, and you can use these to give a polynomial-time algorithm for telling whether a labeling of regions is realizable by a pseudoline arrangment.

The question of whether a pseudoline arrangement can be realized by straight lines exhibits Mnëv universality, which means that it's at least NP-hard (and probably strictly harder). In particular, it is equivalent in complexity to the existential theory of the reals, which is known to be NP-hard, and to be contained in PSPACE.

There is a very nice AMS feature column on oriented matroids. You can read Richter-Gebert's paper "Mnëv Universality Revisited" for a nice discussion and simplification of the proof of Mnëv universality of line arrangements.

Hyperplane arrangements also exhibit Mnëv universality. I don't know offhand of a good reference for this, but it's clear that they have to be at least as hard as line arrangements, and so they are also equivalent to the existential theory of the reals.