Arrangements of approaching pseudo-lines

DOI10.1007/S00454-021-00361-WzbMATH Open1485.52018arXiv2001.08419OpenAlexW4206909371MaRDI QIDQ2117345FDOQ2117345

Stefan Felsner, Patrick Schnider, Alexander Pilz

Publication date: 21 March 2022

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We consider arrangements of $n$ pseudo-lines in the Euclidean plane where each pseudo-line $el{l}_i$ is represented by a bi-infinite connected $x$-monotone curve $f_i(x)$, $xinmathbbR$, s.t. for any two pseudo-lines $el{l}_i$ and $el{l}_j$ with $i<j$, the function $xmapsto{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^{Theta(n^2)}$ isomorphism classes of arrangements of approaching pseudo-lines (while there are only $2^{Theta(nlogn)}$ 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.

Full work available at URL: https://arxiv.org/abs/2001.08419

zbMATH Keywords

discrete geometryorder typespseudo-line arrangements

Mathematics Subject Classification ID

Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cites Work

• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of reduced decompositions of elements of Coxeter groups
• Proof of a conjecture of Burr, Grünbaum, and Sloane
• Teilungen der Ebenen durch Geraden oder topologische Geraden
• Arrangements and Topological Planes
• Semispaces of configurations, cell complexes of arrangements
• Proofs from THE BOOK
• Triangles in Euclidean arrangements
• Helly-type theorems for pseudoline arrangments in \(P^ 2\).
• Suballowable sequences and geometric permutations
• Polynomial realization of pseudoline arrangements
• Every arrangement extends to a spread
• Title not available (Why is that?)
• From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices
• Monotone Simultaneous Embeddings of Upward Planar Digraphs
• Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity

Cited In (1)

• On the Pappus arrangement of lines, forth and back and to the point

This page was built for publication: Arrangements of approaching pseudo-lines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117345)