Improved Bound on the Number of Pseudoline Arrangements via the Zone Theorem
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913724367896576 |
|---|---|
| author | Dallant, Justin |
| author_facet | Dallant, Justin |
| contents | Pseudoline arrangements are fundamental objects in discrete and computational geometry, and different works have tackled the problem of improving the known bounds on the number of simple arrangements of $n$ pseudolines over the past decades. The lower bound in particular has seen two successive improvements in recent years (Dumitrescu and Mandal in 2020 and Cortés Kühnast et al. in 2024). Here we focus on the upper bound, and show that for large enough $n$, there are at most $2^{0.6496n^2}$ different simple arrangements of $n$ pseudolines. This follows a series of incremental improvements starting with work by Knuth in 1992 showing a bound of roughly $2^{0.7925n^2},$ then a bound of $2^{0.6975n^2}$ by Felsner in 1997, and finally the previous best known bound of $2^{0.6572n^2}$ by Felsner and Valtr in 2011. The improved bound presented here follows from a simple argument to combine the approach of this latter work with the use of the Zone Theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_20909 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Bound on the Number of Pseudoline Arrangements via the Zone Theorem Dallant, Justin Computational Geometry Pseudoline arrangements are fundamental objects in discrete and computational geometry, and different works have tackled the problem of improving the known bounds on the number of simple arrangements of $n$ pseudolines over the past decades. The lower bound in particular has seen two successive improvements in recent years (Dumitrescu and Mandal in 2020 and Cortés Kühnast et al. in 2024). Here we focus on the upper bound, and show that for large enough $n$, there are at most $2^{0.6496n^2}$ different simple arrangements of $n$ pseudolines. This follows a series of incremental improvements starting with work by Knuth in 1992 showing a bound of roughly $2^{0.7925n^2},$ then a bound of $2^{0.6975n^2}$ by Felsner in 1997, and finally the previous best known bound of $2^{0.6572n^2}$ by Felsner and Valtr in 2011. The improved bound presented here follows from a simple argument to combine the approach of this latter work with the use of the Zone Theorem. |
| title | Improved Bound on the Number of Pseudoline Arrangements via the Zone Theorem |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2502.20909 |