So we have a lot of line queries in the plane, and for each line query we want to know the number of segments that intersect that line (are stabbed by the line) for a given set of segments in the plane *(not necessarily axis aligned). The set of segments is fixed but the number of query lines could be large. I was thinking about maybe dualizing the problem: Each line segment turns into either an infinite "bow tie" or a horizontal band, and then we can compute the overlay of this arrangement, counting the number of intersecting regions inside each cell. But even though this becomes a pretty nice data structure, query time is still an issue. Any thoughts on how to make preprocessing time and stabbing query time low, assuming there will be a "somewhat large" number of queries (the tradeoff between preprocessing time and total query time is somewhat a parameter in this).
-
$\begingroup$ Apparently, the segments are not necessarily axis-aligned. Are the lines (in the queries) axis-aligned? Are the queries presented in batch form (you know all of the queries in advance before you have to answer any query) or in an online fashion (you must answer each query before you learn what the next query will be)? $\endgroup$D.W.– D.W. ♦03/17/2015 05:21:33Commented Mar 17, 2015 at 5:21
1 Answer 1
Are you familiar with
H. Edelsbrunner, H. A. Maurer, F. P. Preparata, A. L. Rosenberg, E. Welzl, D. Wood. "Stabbing line segments." BIT Numerical Mathematics. 1982, Volume 22, Issue 3, pp 274-281. (Springer link.)
Google Scholar finds more than 100 papers that cite it.
One can use a segment tree data structure, or an interval tree. Segment trees offer $O(\log n + k)$ query time, where $k$ is the number of segments intersected. Space complexity is $O(n \log n)$.