Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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
