arxiv: 2604.23330 · v1 · submitted 2026-04-25 · 💻 cs.CG

Recognition: unknown

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

Daniel Bertschinger , Henry F\"orster , Fabian Klute , Irene Parada , Patrick Schnider , Birgit Vogtenhuber

Authors on Pith no claims yet

Pith reviewed 2026-05-08 06:50 UTC · model grok-4.3

classification 💻 cs.CG

keywords double-wedgesbowtieshourglassesarrangementssegment stabbingpoint-line duality3SUM hardnessGallai-type results

0 comments

The pith

The common intersection of n double-wedges mixing bowties and hourglasses can split into Ω(n²) interior-disjoint regions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies arrangements of double-wedges that may be bowties, which contain no vertical line, or hourglasses, which do contain a vertical line. In this mixed setting the common intersection of n such objects can break into quadratically many separate pieces, a sharp increase from the bowtie-only case studied earlier. The authors supply algorithms that compute the full intersection in worst-case optimal time and locate one point inside it in nearly optimal time, assuming 3SUM has no truly subquadratic algorithm. The geometric equivalence at the heart of the work maps a point common to all double-wedges onto a straight line that stabs one collection of segments while avoiding another.

Core claim

In the generalized setting of double-wedge arrangements that include both bowties and hourglasses, the common intersection of n such double-wedges may consist of Ω(n²) interior-disjoint regions. Algorithms compute this intersection in worst-case optimal running time, and a single intersection point can be found in almost optimal time assuming no truly subquadratic algorithm for 3SUM. A point in the intersection corresponds to a line that stabs segments S corresponding to bowties and avoids segments A from the hourglasses. Gallai-type results for arrangements of segments and anti-segments are also discussed.

What carries the argument

Mixed bowtie-hourglass double-wedges under point-line duality, where a common intersection point equates to a line stabbing one set of segments while avoiding another.

If this is right

The intersection of n double-wedges can be computed in time matching the quadratic size of the output.
Locating any single point inside the intersection requires essentially quadratic time under the 3SUM hypothesis.
Gallai-type statements hold for the dual problem of stabbing some segments while avoiding others.
The quadratic lower bound on the number of regions forces any exact algorithm to output Ω(n²) complexity in the worst case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same duality reduction may transfer quadratic lower bounds to other stabbing-avoidance problems in the plane.
Similar complexity jumps could appear when other geometric objects are allowed to mix two topologically distinct types.
The optimal algorithms described here give a practical baseline for implementing stabbing queries on moderate-sized segment sets.

Load-bearing premise

The point-line duality continues to equate a point in every double-wedge with a stabbing-avoiding line even when bowties and hourglasses are freely mixed.

What would settle it

An explicit collection of n bowties and hourglasses whose common intersection consists of o(n²) interior-disjoint regions, or a truly subquadratic algorithm for finding one intersection point that does not rely on the 3SUM hardness assumption.

Figures

Figures reproduced from arXiv: 2604.23330 by Birgit Vogtenhuber, Daniel Bertschinger, Fabian Klute, Henry F\"orster, Irene Parada, Patrick Schnider.

**Figure 2.** Figure 2: We say that a point x ∈ R 2 is below the upper trace if and only if a vertical ray emerging from x in positive y-direction hits the upper trace. Similarly, a point is above the lower trace if and only if a vertical ray emerging from x in negative y-direction hits the lower trace. If a point is not below the upper trace (or above the lower trace) we say that the point is above it (or below it, respectively) view at source ↗

read the original 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 $\Omega(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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Mixing bowties and hourglasses pushes double-wedge intersections to quadratic complexity with matching algorithms and a 3SUM hardness result for finding one point.

read the letter

The main thing to know is that this paper extends double-wedge intersections from bowties alone to a mixed setting that includes hourglasses, proves an Omega(n squared) lower bound on the number of interior-disjoint regions, and supplies worst-case optimal algorithms plus a near-optimal method to locate one intersection point under the standard 3SUM assumption. The stabbing-avoiding line interpretation is the central new device that makes the mixed case work. They show how a point in the common intersection corresponds to a line that hits every bowtie segment and misses every hourglass complement, then use that to build both the quadratic example and the algorithms. The Gallai-type remarks on segments and anti-segments are a smaller combinatorial aside. The algorithms look grounded in standard arrangement and duality machinery, and the hardness result is stated cleanly without overclaiming. The connection to stabbing problems gives a useful way to think about why the complexity increases and how to compute the regions efficiently. The main soft spot is the duality equivalence itself. The abstract flags that hourglasses change the setting drastically because they contain vertical lines, and the stress-test note correctly flags possible gaps around vertical stabbing lines or boundary coincidences. If those cases are not handled explicitly in the proofs, both the lower-bound construction and the running-time claims could be counting or processing the wrong set of regions. That is the part a referee should check first. This is for computational geometers who already know the bowtie literature and want to see how the mixed case behaves. A reader working on arrangements or geometric set problems will find the bounds and the hardness useful. It deserves a serious referee because the claims are specific, the new interpretation is well-motivated, and the results are concrete enough to verify or refute in detail. I would send it out for peer review.

Referee Report

1 major / 1 minor

Summary. The manuscript examines the common intersection of arrangements of n double-wedges that may be bowties (no vertical line) or hourglasses (contain a vertical line). It claims that the intersection can consist of Ω(n²) interior-disjoint regions, discusses Gallai-type results for segments and anti-segments, provides worst-case optimal algorithms for computing the full intersection, and gives an almost-optimal algorithm for finding one intersection point under the 3SUM-hardness assumption. The central technical device is a re-defined point-line duality equating a point in the common intersection to a line that stabs all segments in S (from bowties) and avoids all segments in A (from hourglass complements).

Significance. If the new duality equivalence is rigorously established for the mixed setting, the Ω(n²) combinatorial bound and the matching optimal-time algorithms constitute a meaningful extension of prior bowtie-only results. The 3SUM-based conditional lower bound for detecting a single intersection point is also a useful addition to the literature on geometric stabbing and avoidance problems.

major comments (1)

[Duality transformation and equivalence (likely §2–3)] The equivalence between membership in the common intersection and the existence of a stabbing/avoiding line (stated in the abstract and used throughout) must be shown to handle vertical lines and all boundary cases where an hourglass boundary coincides with the vertical through the dual point. Because the abstract explicitly states that the mixed bowtie-hourglass setting 'changes the setting drastically' with respect to all prior duality arguments, any gap here would directly affect both the Ω(n²) lower-bound construction and the claimed optimal running times of the algorithms.

minor comments (1)

[Introduction] Notation for bowties versus hourglasses and for the sets S and A should be introduced with a single consistent figure early in the paper.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comment below.

read point-by-point responses

Referee: [Duality transformation and equivalence (likely §2–3)] The equivalence between membership in the common intersection and the existence of a stabbing/avoiding line (stated in the abstract and used throughout) must be shown to handle vertical lines and all boundary cases where an hourglass boundary coincides with the vertical through the dual point. Because the abstract explicitly states that the mixed bowtie-hourglass setting 'changes the setting drastically' with respect to all prior duality arguments, any gap here would directly affect both the Ω(n²) lower-bound construction and the claimed optimal running times of the algorithms.

Authors: We agree that the equivalence must be rigorously established for vertical lines and all boundary cases, given the mixed setting and the abstract's statement that it changes the duality arguments drastically. The manuscript redefines the point-line duality in Section 2 to equate a point in the common intersection with a line stabbing segments in S (from bowties) and avoiding segments in A (from hourglass complements). However, we acknowledge that the current presentation may not explicitly enumerate every boundary case. In the revised manuscript we will add a dedicated case analysis in §2 proving the equivalence holds when the dual line is vertical (consistent with hourglasses containing a vertical line by definition) and when an hourglass boundary coincides with the vertical through the dual point. The analysis will distinguish closed versus open wedges to confirm exact correspondence with intersection membership. This clarification strengthens the foundation but leaves the Ω(n²) bound, Gallai-type results, and the optimal-time algorithms unchanged, as the additional cases are resolved within the existing combinatorial and algorithmic framework. revision: yes

Circularity Check

0 steps flagged

No circularity; duality equivalence and bounds are independently derived

full rationale

The paper states the point-line duality equivalence for the mixed bowtie-hourglass case as a direct geometric correspondence (a point in the common intersection iff the dual line stabs S and avoids A). This is not self-definitional or fitted; it is a rephrasing that enables the subsequent combinatorial and algorithmic results. The Ω(n²) lower bound follows from explicit construction of arrangements, the algorithms achieve worst-case optimal time via standard sweep or divide-and-conquer techniques on the dual segments, and the single-point finding uses a 3SUM-hardness reduction that is external and conditional. No load-bearing self-citation, ansatz smuggling, or renaming of known results occurs; the generalization is handled explicitly without reducing claims to their own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the point-line duality equivalence for mixed double-wedges and standard properties of line arrangements from prior literature; no free parameters or new entities are introduced in the abstract.

axioms (1)

domain assumption Point-line duality maps the intersection of double-wedges to lines stabbing some segments while avoiding others, even when hourglasses are included.
Explicitly invoked in the abstract as the key change from earlier bowtie-only studies.

pith-pipeline@v0.9.0 · 5535 in / 1397 out tokens · 41051 ms · 2026-05-08T06:50:50.649146+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references

[1]

Abboud and V

1A. Abboud and V. Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014), pages 434–443,

2014
[2]

Pătraşcu

14 M. Pătraşcu. Towards polynomial lower bounds for dynamic problems. In L. J. Schulman, editor,Proceedings of the 42nd ACM Symposium on Theory of Computing, (STOC 2010), pages 603–610,

2010
[3]

15 C. D. Toth, J. O’Rourke, and J. E. Goodman.Handbook of Discrete and Computational Geometry. CRC press, third edition, 2017

2017