Arrangement of pseudolines

{{Short description|Pseudolines arranged largely to study arrangements of lines}}

File:Pappos pseudo.svg]]

File:Wiring diagram.svg

An arrangement of pseudolines is a family of curves that share similar topological properties with a line arrangement.

{{citation

| last = Grünbaum | first = B. | author-link = Branko Grünbaum

| location = Providence, R.I.

| publisher = American Mathematical Society

| series = Regional Conference Series in Mathematics

| title = Arrangements and Spreads

| volume = 10

| page = 40

| year = 1972}}

{{citation

| last1 = Agarwal

| first1 = P. K.

| author1-link = Pankaj K. Agarwal

| last2 = Sharir

| first2 = M.

| author2-link = Micha Sharir

| contribution = Pseudo-line arrangements: duality, algorithms, and applications

| location = San Francisco

| pages = 800–809

| publisher = Society for Industrial and Applied Mathematics

| title = Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02)

| contribution-url = http://portal.acm.org/citation.cfm?id=545486

| year = 2002

| title-link = Symposium on Discrete Algorithms

}}

Most commonly, in the study of arrangements of lines, these have the simple property that each crosses every other line exactly once. These can be defined in the projective plane as simple closed curves any two of which meet in a single crossing point.

{{citation

| last1 = Eppstein | first1 = D. | author1-link = David Eppstein

| last2 = Falmagne | first2 = J.-Cl. | author2-link = Jean-Claude Falmagne

| last3 = Ovchinnikov | first3 = S.

| publisher = Springer-Verlag

| title = Media Theory

| year = 2007}}

Furthermore, in a simple arrangement, along with all lines being required to cross all others, no 3 pseudolines may cross at the same point.

A pseudoline arrangement is said to be stretchable if it is combinatorially equivalent to a line arrangement, meaning that you can straighten each one while maintaining the order in which each crosses each other. Stretchability is the problem of deciding for a given pseudoline arrangement if it is equivalent to a line

arrangement, and simple stretchability is the same problem but for simple arrangements. Determining stretchability is a difficult computational task: it is complete for the existential theory of the reals to distinguish stretchable arrangements from non-stretchable ones,

{{citation

| last = Shor | first = P. W. | authorlink = Peter Shor

| contribution = Stretchability of pseudolines is NP-hard

| editor1-last = Gritzmann | editor1-first = P.

| editor2-last = Sturmfels | editor2-first = B. | editor2-link = Bernd Sturmfels

| location = Providence, R.I.

| pages = 531–554

| publisher = American Mathematical Society

| series = DIMACS Series in Discrete Mathematics and Theoretical Computer Science

| title = Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift

| url = https://math.mit.edu/~shor/papers/Stretchability_NP-hard.pdf

| volume = 4

| year = 1991

}}

{{citation|first=Marcus|last=Schaefer|contribution=Complexity of some geometric and topological problems|contribution-url=http://ovid.cs.depaul.edu/documents/convex.pdf|title=Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|volume=5849|pages=334–344|doi=10.1007/978-3-642-11805-0_32|year=2010|title-link=International Symposium on Graph Drawing|isbn=978-3-642-11804-3|doi-access=free|access-date=2024-10-16|archive-date=2021-06-26|archive-url=https://web.archive.org/web/20210626212759/http://ovid.cs.depaul.edu/documents/convex.pdf|url-status=live}}

while determining simple stretchability is NP-hard. Algorithms do exist for stretchability, such as Bokowski’s rubber-band method,

{{citation

| last = Bokowski | first = Jürgen

| title = On Heuristic Methods for Finding Realizations of Surfaces

| editor1-last = Bobenko | editor1-first = A. I.

| editor2-last = Schröder | editor2-first = P.

| editor3-last = Sullivan | editor3-first = J. M.

| editor4-last = Ziegler | editor4-first = G. M.

| contribution = On Heuristic Methods for Finding Realizations of Surfaces

| series = Oberwolfach Seminars

| volume = 38

| pages = 255–260

| year = 2008

| publisher = Birkhäuser Verlag

| location = Basel, Switzerland

| isbn = 978-3-7643-8621-4

| url = https://www.researchgate.net/publication/227200409_On_Heuristic_Methods_for_Finding_Realizations_of_Surfaces

| access-date = 2025-06-19

}}

the final polynomial method,

{{citation

| last = Lombardi | first = Henri

| title = Nullstellensatz réel effectif et variantes

| journal = C. R. Acad. Sci. Paris, Série I

| volume = 310

| pages = 635–640

| year = 1990

| series = Théorie des Nombres, Besançon

| issue = Fascicule 1

| publisher = Université de Franche-Comté

| url = https://www.numdam.org/item/10.5802/pmb.a-60.pdf

| access-date = 2025-06-19

}}

{{citation

| last1 = Fukuda | first1 = Komei

| last2 = Miyata | first2 = Hiroyuki

| last3 = Moriyama | first3 = Sonoko

| title = Complete Enumeration of Small Realizable Oriented Matroids

| journal = Discrete & Computational Geometry

| volume = 49

| pages = 359–381

| year = 2013

| doi = 10.1007/s00454-012-9493-7

| url = https://arxiv.org/pdf/1204.0645

| access-date = 2025-06-19

}}

the solvability sequence method, and the inequality reduction method.

{{citation

| last1 = Bokowski | first1 = Jürgen

| last2 = Sturmfels | first2 = Bernd

| title = Computational Synthetic Geometry

| series = Lecture Notes in Mathematics

| volume = 1355

| publisher = Springer-Verlag Berlin Heidelberg

| year = 1989

| isbn = 978-3-540-50478-8

| doi = 10.1007/BFb0089253

| url = https://doi.org/10.1007/BFb0089253

| access-date = 2025-06-19

}}

These take advantage of the fact that the problem of stretchability is equivalent to the problem of the realization of a rank-3 oriented matroid.

Every arrangement of finitely many pseudolines can be extended so that they become lines in a "spread", a type of non-Euclidean incidence geometry in which every two points of a topological plane are connected by a unique line (as in the Euclidean plane) but in which other axioms of Euclidean geometry may not apply.

{{citation

| last1 = Goodman | first1 = Jacob E. | author1-link = Jacob E. Goodman

| last2 = Pollack | first2 = Richard | author2-link = Richard M. Pollack

| last3 = Wenger | first3 = Rephael

| last4 = Zamfirescu | first4 = Tudor

| doi = 10.1007/BF01212978

| issue = 3

| journal = Combinatorica

| mr = 1305899

| pages = 301–306

| title = Every arrangement extends to a spread

| volume = 14

| year = 1994| s2cid = 42055590 }}

Notable arrangements of pseudolines which cannot be stretched include the arrangement of 9 pseudolines constructed by Friedrich Levi which violates the theorem of Pappus, and a 10 pseudoline arrangement constructed to violate Desargues's theorem.

{{cite book

| last1 = Felsner

| first1 = Stefan

| last2 = Goodman

| first2 = Jacob E.

| title = Handbook of Discrete and Computational Geometry

| edition = 3rd

| date = 2017

| publisher = Chapman and Hall/CRC

| chapter = Pseudoline Arrangements

| chapter-url = https://www.csun.edu/~ctoth/Handbook/chap5.pdf

| isbn = 9781315119601

}}

Felsner and Valtr proved in 2009 that for an arrangement of $n$ pseudolines, there are at most $2^\{0.657n^2\}$ simple arrangements. This improves upon the previous bounds of $2^\{0.792n^2\}$ in 1992 and $2^\{0.697n^2\}$ in 1997. {{cite journal

| last1 = Felsner

| first1 = Stefan

| last2 = Valtr

| first2 = Pavel

| title = Coding and Counting Arrangements of Pseudolines

| journal = Discrete & Computational Geometry

| volume = 46

| issue = 3

| pages = 405–416

| date = 2011

| doi = 10.1007/s00454-011-9366-4

| url = https://link.springer.com/content/pdf/10.1007/s00454-011-9366-4.pdf

| access-date = 2025-06-19

| publisher = Springer Science+Business Media

}} The number of simple arrangements of {{mvar|n}} pseudolines in the projective plane with a marked cell is known up to {{mvar|n}}=13:

1, 1, 1, 2, 3, 16, 135, 3315, 158830, 14320182, 2343203071, 691470685682, 366477801792538 {{OEIS|id=A006247}}

A common diagram used to represent an arrangement is the wiring diagram, a series of parallel lines with crossings between them drawn as an "X" in a simple crossing. When drawn this way, they can be described with notation for either the order in which each line crosses the other, the state of the orders between each crossing (or allowed groups of crossing whose orders do not matter), or as a list of pairs, each pair being the labels of 2 lines which have crossed, ordered in a given direction (usually left to right). They draw similarities to braids, although without any need to keep track of which crosses atop the other, the crossings may be seen as elements of the Coxeter group.

Two arrangements are said to be "related by a triangle-flip" if one of them can be transformed into the other by changing the orientation of a single triangular face, or in other words, by moving one of the three pseudolines that form the triangle across the intersection of the other two. For any two simple wiring diagrams numbered 1 through {{mvar|n}} in order, one can be transformed into the other with a sequence of these triangle-flips (and vice versa). This fact has counterparts in the terminology of mutations on oriented matroids and Coxeter relations for reduced decomposition.

File:Non-approaching vs. approaching pseudolines.png

An arrangement of approaching pseudolines is an arrangement of pseudolines where each pair of pseudolines approach each other until they cross, and then they move away from

each other. There are arrangements of pseudolines that are not realizable with approaching pseudolines, and these are thus not stretchable in general. However, not all approaching arrangements can be stretched.{{cite journal

| last1 = Felsner

| first1 = Stefan

| last2 = Pilz

| first2 = Alexander

| last3 = Schnider

| first3 = Patrick

| title = Arrangements of Approaching Pseudo-Lines

| journal = Discrete & Computational Geometry

| volume = 67

| issue = 2

| pages = 380–402

| year = 2022

| doi = 10.1007/s00454-021-00361-w

| url = https://link.springer.com/content/pdf/10.1007/s00454-021-00361-w.pdf

| access-date = 2025-06-14

| publisher = Springer

}}