2026/04/25 by Daniel Bertschinger, Henry Förster, Fabian Klute +3 · 2 voices
Computer Science · #cs.CG
paper · pdf · doi:10.1016/j.ipl.2026.106642
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 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 Ω(n2) 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.