# Data structure to query intersection of a line and a set of line segments

We want to pre-process a set $$S$$ of $$n$$ line segments into a data structure, such that we can answer some queries: Given a query line $$l$$, report how many line segments in $$S$$ does it intersect.

It is required that the query should be done in $$O(\log{n})$$ time. The data structure itself should take up to $$O(n^{2})$$ storage and be built in $$O(n^{2}\log{n})$$ time. It is suggested that it should be done in dual plane.

I understand that the question may require me to look for the number of double wedge that the a query point is in, but I can't think of any efficient data structure to report such information. Any suggestions?

This question is basically a homework question from the textbook Computational Geometry by de Berg et al (Question 8.15). I would like to apologize that this question may not be exciting to you.

Edit: Yes it is in $$\mathbb{R}^{2}$$. By query point I mean the query line dualised into a point on dual plane.