论文标题
接近伪线的安排
Arrangements of Approaching Pseudo-Lines
论文作者
论文摘要
我们考虑在欧几里得飞机上的$ n $伪线安排，每个伪线$ \ ell_i $由双式二线连接的$ x $ -Monotone Curve $ f_i（x）$，$ x \ in \ mathbb {r} $ el_ Ell_ $ el_ y y y y y y y y y y y y y y y y yi yi yi yi yi yi yi yi yi yi yi yi yi yi yi yi yi yi yi; j $，功能$ x \ mapsto f_j（x） - f_i（x）$单调降低和过滤（即，伪线接近彼此直至交叉，然后彼此移开）。我们表明，在某些方面，这种接近伪线的安排与线路的安排相似，而对于其他方面，它们具有一般伪线安排的自由。 对于前者而言，我们证明：1。有一些伪线安排在接近伪线方面无法实现。 2。接近伪线的每一个安排都具有与接近伪线的基本布置的双重概括配置。 对于后者，我们显示：1。有$ 2^{θ（n^2）} $同构的接近伪线的安排类别（而只有$ 2^{θ（n \ log n）} $ shepements的$ 2^{θ（n \ log n）} $等法类别。 2。可以在多项式时间内确定允许序列是否可以通过接近伪线的排列来实现。 此外，接近伪线的排列可以通过翻转三角形细胞（即它们具有连接的翻转图）相互转化，并且这种类型的每种双分化排列都包含一个双向三角细胞。
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^{Θ(n^2)}$ isomorphism classes of arrangements of approaching pseudo-lines (while there are only $2^{Θ(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.
