Bowties and Hourglasses: Intersections of Double-Wedges Or: Stabbing and Avoiding Line Segments

• Consider arrangements where double-wedges may be both bowties or hourglasses. • Gallai-type results for arrangements of segments and anti-segments. • Worst-case optimal algorithms for computing the intersection of double-wedges. • Finding a single intersection point is 3SUM-hard, so it is unlikely to admit a truly subquadratic algorithm. We study the common intersection of arrangements of double-wedges. We consider arrangements where double-wedges may be both 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 S (corresponding to the bowties) while it avoids a different set of segments 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.