Arrangements of approaching pseudo-lines

DOI10.1007/S00454-021-00361-WMaRDI QIDQ2117345zbMATH OpenOpenAlexFDO

Authors Alexander Pilz, Patrick Schnider, Stefan Felsner

Publication date 21 March 2022

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

Copyright license Creative Commons Attribution 4.0 International

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)

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.

Recommendations

• scientific article; zbMATH DE number 1182898
• Arrangements of double pseudolines
• On the number of arrangements of pseudolines
• Pseudo-Line Arrangements: Duality, Algorithms, and Applications
• Extremal configurations and levels in pseudoline arrangements.

Cites work

• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 53152 (Why is no real title available?)
• scientific article; zbMATH DE number 1124651 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• Arrangements and Topological Planes
• Drawing arrangement graphs in small grids, or how to play Planarity
• Every arrangement extends to a spread
• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices
• Helly-type theorems for pseudoline arrangments in P^ 2.
• Monotone simultaneous embeddings of upward planar digraphs
• On the number of reduced decompositions of elements of Coxeter groups
• Polynomial realization of pseudoline arrangements
• Proof of a conjecture of Burr, Grünbaum, and Sloane
• Proofs from THE BOOK
• Semispaces of configurations, cell complexes of arrangements
• Suballowable sequences and geometric permutations
• Teilungen der Ebenen durch Geraden oder topologische Geraden
• Triangles in Euclidean arrangements
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)

Cited in

(2)

• On the Pappus arrangement of lines, forth and back and to the point
• scientific article; zbMATH DE number 3903453 (Why is no real title available?)

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)