<p>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. </p>

<p>The question of whether a pseudoline arrangement can be realized by straight lines
exhibits <a href="http://en.wikipedia.org/wiki/Mnev%27s_universality_theorem">Mnëv universality</a>, 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.</p>

<p>There is a very nice <a href="http://www.ams.org/samplings/feature-column/fcarc-oriented4">AMS feature column</a> on oriented matroids. You can read Richter-Gebert's paper <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.1426">"Mnëv Universality Revisited"</a> for a nice discussion and simplification of the proof of Mnëv universality of line arrangements. </p>

<p>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. </p>

CC BY-SA 3.0
2013-07-16T22:49:24.640Z
2013-07-16T23:15:29.340Z
2013-07-16T23:15:29.340Z
Peter Shor 
<p>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.) </p>

<p>Say that a subset $S$ of $\{+1,-1\}^n$ is <em>realizable by a linear arrangement</em> 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.</p>

<reference-request><convex-geometry><computational-geometry>
Configurations from arrangement of lines
arnab
# Configurations from arrangement of lines

(Asked by: username_0 on 2013-07-16)

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.

**Tags:** reference-request, convex-geometry, computational-geometry

---

## 1 answers

### Answer by username_1 on 2013-07-16. Score: 9 | Accepted answer

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](http://en.wikipedia.org/wiki/Mnev%27s_universality_theorem), 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](http://www.ams.org/samplings/feature-column/fcarc-oriented4) on oriented matroids. You can read Richter-Gebert's paper ["Mnëv Universality Revisited"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.1426) 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.


---

