DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.43

An Improved Lower Bound on the Number of Pseudoline Arrangements

Authors: Fernando Cortés Kühnast, Justin Dallant, Stefan Felsner, and Manfred Scheucher

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

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.

Cite as

Fernando Cortés Kühnast, Justin Dallant, Stefan Felsner, and Manfred Scheucher. An Improved Lower Bound on the Number of Pseudoline Arrangements. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{corteskuhnast_et_al:LIPIcs.SoCG.2024.43,
  author =	{Cort\'{e}s K\"{u}hnast, Fernando and Dallant, Justin and Felsner, Stefan and Scheucher, Manfred},
  title =	{{An Improved Lower Bound on the Number of Pseudoline Arrangements}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.43},
  URN =		{urn:nbn:de:0030-drops-199880},
  doi =		{10.4230/LIPIcs.SoCG.2024.43},
  annote =	{Keywords: counting, pseudoline arrangement, recursive construction, bipermutation, divide and conquer, dynamic programming, computer-assisted proof}
}

Search Results

Documents authored by Cortés Kühnast, Fernando

An Improved Lower Bound on the Number of Pseudoline Arrangements

Abstract

Cite as

Thanks for your feedback!

Could not send message