Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments)
For computational geometry researchers, this work generalizes previous results on double-wedge intersections and provides tight bounds and algorithms, though the contribution is incremental.
This paper studies the intersection of arrangements of double-wedges, including both bowties and hourglasses, showing that the intersection can consist of Ω(n²) interior-disjoint regions. It provides algorithms for computing the intersection with worst-case optimal running time and finds a single intersection point in almost optimal time under the 3SUM hardness assumption.
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.