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?


This is equivalent to two ray shooting queries.

There is a tradeoff in space and query time. For any $n< m<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]

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.