Arrangements of Approaching Pseudo-Lines

Stefan Felsner, Alexander Pilz, Patrick Schnider*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


We consider arrangements of n pseudo-lines in the Euclidean plane where each pseudo-line ℓi is represented by a bi-infinite connected x-monotone curve fi(x) , x∈ R, such that for any two pseudo-lines ℓi and ℓj with i<j, the function x↦fj(x)-fi(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 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:There are arrangements of pseudo-lines that are not realizable with approaching pseudo-lines.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:There are 2Θ(n2) isomorphism classes of arrangements of approaching pseudo-lines (while there are only 2 Θ(nlogn) isomorphism classes of line arrangements).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.

Original languageEnglish
Pages (from-to)380-402
Number of pages23
JournalDiscrete and Computational Geometry
Issue number2
Publication statusPublished - Mar 2022


  • Discrete geometry
  • Order types
  • Pseudo-line arrangements

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Arrangements of Approaching Pseudo-Lines'. Together they form a unique fingerprint.

Cite this