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).
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)$.