Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments)

Daniel Bertschinger, Henry Förster, Fabian Klute, Irene Parada, Patrick Schnider, Birgit Vogtenhuber

TL;DR

This paper generalizes the classic geometric problem of finding a line that intersects ("stabs") a set of segments to a much harder variant: stabbing one set of segments while completely avoiding another. By analyzing this problem through the lens of "bowtie" and "hourglass" double-wedge intersections, the authors establish tight combinatorial bounds, prove 3SUM-hardness for finding even a single solution, and provide worst-case optimal algorithms.

What Problem Does This Paper Address?

In computational geometry, point-line duality is a powerful tool. A classic problem involves finding a "stabbing line" that intersects a given set of $n$ line segments in a plane. Using duality, this is equivalent to finding a single point that lies within the common intersection of $n$ "double-wedges" shaped like bowties (which do not contain a vertical line). This classic problem is well-behaved: the intersection forms a single connected region of $O(n)$ complexity, solvable in $O(n \log n)$ time.

This paper addresses what happens when you introduce "hourglasses"—double-wedges that do contain a vertical line. Dually, an hourglass represents an "anti-segment" (a full line minus a segment). Finding a point in the intersection of both bowties and hourglasses translates to finding a line that stabs a set of target segments $\mathcal{S}$ while completely avoiding a set of forbidden segments $\mathcal{A}$. The authors explore how this generalization fundamentally alters the problem's combinatorial complexity, algorithmic runtime, and geometric properties.

Methods

The authors employ a mix of combinatorial geometry constructions, dual transformations, and complexity reductions:

  1. Projective Duality Mapping: They use standard projective duality $T$ to map points $(p_x, p_y)$ to non-vertical lines $y = p_x \cdot x - p_y$. This maps bowties to line segments and hourglasses to anti-segments.
  2. Grating Constructions: To test combinatorial limits, they construct a "vertical grating" of bowties intersected with a perpendicular "horizontal grating" of hourglasses, creating a complex grid-like interference pattern.
  3. Line Arrangement Algorithms: For the general algorithmic solution, they construct a line arrangement using a Doubly-Connected Edge List (DCEL) data structure. They apply the Zone theorem to build it incrementally and then traverse the cells using a Breadth-First Search (BFS) on the dual graph to track double-wedge containment counts in constant time per cell transition.
  4. Hardness Reduction: To prove computational complexity, they reduce GeomBase (a known 3SUM-hard problem where one must find a non-horizontal line passing through three points on three specific horizontal lines) to their "Stabbing and Avoiding Segments" problem. They do this by turning the points into tiny $\epsilon$-radius gaps within a series of blocking segments.

Datasets

Not discussed in the paper. This is a purely theoretical and algorithmic paper; no empirical datasets or benchmarks were used.

Key Insights and Ideas

  • Complexity Explosion: Moving from pure bowties to a mix of bowties and hourglasses causes a massive jump in geometric complexity. While pure bowties yield a single region of $O(n)$ complexity, adding hourglasses allows the intersection to fracture into a grid-like pattern of $\Omega(n^2)$ disconnected valid regions.
  • Hardness of a Single Point: Usually, finding all valid regions takes longer than finding just one valid point. Surprisingly, the authors show that even deciding if a single valid stabbing/avoiding line exists is 3SUM-hard. This implies that we likely cannot design a truly subquadratic algorithm ($O(n^{2-\varepsilon})$) even for the decision version of the problem.
  • Gallai/Helly Extensions: The paper extends Helly-type properties (which look at when local intersection properties imply global intersection properties) to anti-segments. They prove that if any 3 elements in a mixed family of segments and anti-segments can be pierced by a line, then the entire family can be pierced by 4 lines. They also show a lower bound where 3 lines are strictly necessary.

Key Results

  • Combinatorial Complexity: Proved that the intersection of $n$ double-wedges can consist of $\Omega(n^2)$ interior-disjoint regions.
  • Worst-Case Optimal Algorithms:
  • Developed an $O(n^2)$ time algorithm to compute the full intersection of $n$ double-wedges in the general setting, which is worst-case optimal due to the $\Omega(n^2)$ region complexity.
  • Provided an optimized $O((k^2 + nk) \log(n + k^2))$ time algorithm for scenarios where only a few ($k \ll n$) hourglasses are present.
  • Demonstrated that if the double-wedges do not cover all slopes, the problem can be rotated and solved in $O(n \log n)$ time.
  • Computational Hardness: Proved that finding a single intersection point (or a valid stabbing/avoiding line) cannot be done in subquadratic time ($O(n^{2-\varepsilon})$) unless the widely believed 3SUM conjecture is false.

Limitations and Future Work

  • The Pure Segment Gap: The authors leave open a classic question regarding pure line segments: If any three segments in a family can be pierced by a line, do two lines always suffice to pierce the entire family? A positive answer to this would make their mixed-setting bound of 3 lines completely tight.
  • Higher Dimensions: The current work is strictly limited to the 2D plane ($\mathbb{R}^2$). The authors note that generalizing double-wedge arrangements and stabbing/avoiding problems to higher dimensions remains an open and highly intriguing challenge.

Summary updated

Abstract

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.
BibTeX
@article{bertschinger2026bowties,
  author = {Daniel Bertschinger and Henry Förster and Fabian Klute and Irene Parada and Patrick Schnider and Birgit Vogtenhuber},
  title = {{Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments)}},
  journal = {Inf. Process. Lett.},
  year = {2026},
  doi = {10.1016/j.ipl.2026.106642},
}

Loading related content...

Figure