Arrangements of Pseudocircles: On Digons and Triangles
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909467301380096 |
|---|---|
| author | Felsner, Stefan Roch, Sandro Scheucher, Manfred |
| author_facet | Felsner, Stefan Roch, Sandro Scheucher, Manfred |
| contents | In this article, we study the cell-structure of simple arrangements of pairwise intersecting pseudocircles. The focus will be on two problems of Grünbaum (1972).
First, we discuss the maximum number of digons or touching points. Grünbaum conjectured that there are at most $2n - 2$ digon cells or equivalently at most $2n - 2$ touchings. Agarwal et al. (2004) verified the conjecture for cylindrical arrangements. We show that the conjecture holds for any arrangement which contains three pairwise touching pseudocircles. The proof makes use of the result for cylindrical arrangements. Moreover, we construct non-cylindrical arrangements which attain the maximum of $2n - 2$ touchings and have no triple of pairwise touching pseudocircles.
Second, we discuss the minimum number of triangular cells (triangles) in arrangements without digons and touchings. Grünbaum conjectured that such arrangements have $2n - 4$ triangles. Snoeyink and Hershberger (1991) established a lower bound of $\lceil \frac{4}{3}n \rceil$. Felsner and Scheucher (2017) disproved the conjecture and constructed a family of arrangements with only $\lceil \frac{16}{11}n \rceil$ triangles. We provide a construction which shows that $\lceil \frac{4}{3}n \rceil$ is the correct value. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_12110 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Arrangements of Pseudocircles: On Digons and Triangles Felsner, Stefan Roch, Sandro Scheucher, Manfred Computational Geometry Combinatorics 52Cxx I.3.5; G.2.1 In this article, we study the cell-structure of simple arrangements of pairwise intersecting pseudocircles. The focus will be on two problems of Grünbaum (1972). First, we discuss the maximum number of digons or touching points. Grünbaum conjectured that there are at most $2n - 2$ digon cells or equivalently at most $2n - 2$ touchings. Agarwal et al. (2004) verified the conjecture for cylindrical arrangements. We show that the conjecture holds for any arrangement which contains three pairwise touching pseudocircles. The proof makes use of the result for cylindrical arrangements. Moreover, we construct non-cylindrical arrangements which attain the maximum of $2n - 2$ touchings and have no triple of pairwise touching pseudocircles. Second, we discuss the minimum number of triangular cells (triangles) in arrangements without digons and touchings. Grünbaum conjectured that such arrangements have $2n - 4$ triangles. Snoeyink and Hershberger (1991) established a lower bound of $\lceil \frac{4}{3}n \rceil$. Felsner and Scheucher (2017) disproved the conjecture and constructed a family of arrangements with only $\lceil \frac{16}{11}n \rceil$ triangles. We provide a construction which shows that $\lceil \frac{4}{3}n \rceil$ is the correct value. |
| title | Arrangements of Pseudocircles: On Digons and Triangles |
| topic | Computational Geometry Combinatorics 52Cxx I.3.5; G.2.1 |
| url | https://arxiv.org/abs/2208.12110 |