Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments)
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917436686598144 |
|---|---|
| author | Bertschinger, Daniel Förster, Henry Klute, Fabian Parada, Irene Schnider, Patrick Vogtenhuber, Birgit |
| author_facet | Bertschinger, Daniel Förster, Henry Klute, Fabian Parada, Irene Schnider, Patrick Vogtenhuber, Birgit |
| contents | We study the common intersection of arrangements of double-wedges. We consider arrangements where double-wedges may be either bowties (which do not contain a vertical line) or hourglasses (which contain a vertical line), in contrast to earlier studies that focused on arrangements of only bowties. This generalization changes the setting drastically, in particular, with respect to all arguments involving the point-line duality. Namely, a point in the intersection of all double-wedges is equivalent to a line that stabs a set of segments $\mathcal{S}$ (corresponding to the bowties) while it avoids a different set of segments $\mathcal{A}$ (corresponding to the complement of the hourglasses).
We show that in this general setting, the intersection of $n$ double-wedges may consist of $Ω(n^2)$ interior-disjoint regions. Further, we discuss Gallai-type results for arrangements of segments and anti-segments, and we provide algorithms for computing the intersection of such arrangements with worst-case optimal running time. Finally, we also prove that we can find a single intersection point in almost optimal running time, assuming that 3SUM admits no truly subquadratic-time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23330 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments) Bertschinger, Daniel Förster, Henry Klute, Fabian Parada, Irene Schnider, Patrick Vogtenhuber, Birgit Computational Geometry We study the common intersection of arrangements of double-wedges. We consider arrangements where double-wedges may be either bowties (which do not contain a vertical line) or hourglasses (which contain a vertical line), in contrast to earlier studies that focused on arrangements of only bowties. This generalization changes the setting drastically, in particular, with respect to all arguments involving the point-line duality. Namely, a point in the intersection of all double-wedges is equivalent to a line that stabs a set of segments $\mathcal{S}$ (corresponding to the bowties) while it avoids a different set of segments $\mathcal{A}$ (corresponding to the complement of the hourglasses). We show that in this general setting, the intersection of $n$ double-wedges may consist of $Ω(n^2)$ interior-disjoint regions. Further, we discuss Gallai-type results for arrangements of segments and anti-segments, and we provide algorithms for computing the intersection of such arrangements with worst-case optimal running time. Finally, we also prove that we can find a single intersection point in almost optimal running time, assuming that 3SUM admits no truly subquadratic-time algorithm. |
| title | Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments) |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2604.23330 |