<p>This is equivalent to two ray shooting queries.</p>

<p>There is a tradeoff in space and query time. For any $n&lt; m&lt;n^2$, there is an data structure that returns result in $O(\frac{n}{\sqrt{m}} \log^{O(1)}(n))$ time using $O(m^{1+\epsilon})$ space. [1]</p>

<p>[1] Pankaj K. Agarwal and Jiří Matoušek, <em>Ray Shooting and Parametric Search</em>, SIAM Journal on Computing 1993 22:4, 794-806</p>

CC BY-SA 3.0
2015-03-28T08:39:20.450Z
2015-03-28T08:39:20.450Z
Chao Xu
<p>Store a set of 2d segments S in some data structure. For an arbitrary query 2d segment q, answer a yes/no question in sublinear time: whether q intersect with any segment in S? </p>

<p>If the query is a vertical or horizontal segment, it can be solved by 2D segment tree in O(logn).The preprocessing is to sort the x-coordinates or y-coordinates of end points. But how about an arbitrary segment query? </p>

<cg.comp-geom>
arbitrary segment stabbing query for 2d segments
Yan Zhu
# arbitrary segment stabbing query for 2d segments

(Asked by: username_0 on 2015-03-28)

Store a set of 2d segments S in some data structure. For an arbitrary query 2d segment q, answer a yes/no question in sublinear time: whether q intersect with any segment in S?

If the query is a vertical or horizontal segment, it can be solved by 2D segment tree in O(logn).The preprocessing is to sort the x-coordinates or y-coordinates of end points. But how about an arbitrary segment query?

**Tags:** cg.comp-geom


---

## 1 answers

### Answer by username_1 on 2015-03-28. Score: 2

This is equivalent to two ray shooting queries.

There is a tradeoff in space and query time. For any $n< m

[1] Pankaj K. Agarwal and Jiří Matoušek, *Ray Shooting and Parametric Search*, SIAM Journal on Computing 1993 22:4, 794-806


---

