Arrangements of Approaching Pseudo-Lines

Abstract

We consider arrangements of $n$ pseudo-lines in the Euclidean plane where each pseudo-line ${\ell }_i$ is represented by a bi-infinite connected $x$-monotone curve $f_i(x)$, $x\in \mathbb{R}$, s.t.\ for any two pseudo-lines ${\ell }_i$ and ${\ell }_j$ with $i<j$, the function $x\mapsto f_j(x)-f_i(x)$ is monotonically decreasing and surjective (i.e., the pseudo-lines approach each other until they cross, and then move away from each other). We show that such \emph{arrangements of approaching pseudo-lines}, under some aspects, behave similar to arrangements of lines, while for other aspects, they share the freedom of general pseudo-line arrangements. For the former, we prove: 1. There are arrangements of pseudo-lines that are not realizable with approaching pseudo-lines. 2. Every arrangement of approaching pseudo-lines has a dual generalized configuration of points with an underlying arrangement of approaching pseudo-lines. For the latter, we show: 1. There are $2^{\hat{I}˜(n^2)}$ isomorphism classes of arrangements of approaching pseudo-lines (while there are only $2^{\hat{I}˜(n\log n)}$ isomorphism classes of line arrangements). 2. It can be decided in polynomial time whether an allowable sequence is realizable by an arrangement of approaching pseudo-lines. Furthermore, arrangements of approaching pseudo-lines can be transformed into each other by flipping triangular cells, i.e., they have a connected flip graph, and every bichromatic arrangement of this type contains a bichromatic triangular cell.