2026-07-23T20:05:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19988 2024-06-06T06:21:15Z ddc:004 open_access

An Improved Lower Bound on the Number of Pseudoline Arrangements Cortés Kühnast, Fernando Dallant, Justin Felsner, Stefan Scheucher, Manfred counting pseudoline arrangement recursive construction bipermutation divide and conquer dynamic programming computer-assisted proof Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number B_n of non-isomorphic simple arrangements of n pseudolines goes back to Goodman and Pollack, Knuth, and others. It is known that B_n is in the order of 2^Θ(n²) and finding asymptotic bounds on b_n = log₂(B_n)/n² remains a challenging task. In 2011, Felsner and Valtr showed that 0.1887 ≤ b_n ≤ 0.6571 for sufficiently large n. The upper bound remains untouched but in 2020 Dumitrescu and Mandal improved the lower bound constant to 0.2083. Their approach utilizes the known values of B_n for up to n = 12. We tackle the lower bound by utilizing dynamic programming and the Lindström–Gessel–Viennot lemma. Our new bound is b_n ≥ 0.2721 for sufficiently large n. The result is based on a delicate interplay of theoretical ideas and computer assistance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fernando Cortés Kühnast and Justin Dallant and Stefan Felsner and Manfred Scheucher 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.43 urn:nbn:de:0030-drops-199880 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.43 eng https://creativecommons.org/licenses/by/4.0/legalcode