# 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.

HERE is the solution I did in the homework but it still lose three points on:

(3 points) Construct the O(n^2) faces with proper intersection counts of each faces.   • Are you the one who asked the original question? Apr 1 at 16:15
• It is a bit problematic to add an answer which you know is (slightly) wrong, without at least pointing out potential problems in it. Apr 1 at 16:15
• We'd prefer that you not use images as main content of your post. This makes your answer impossible to search and inaccessible to the visually impaired; we don't like that. It would be better to transcribe text and mathematics. You can use LaTeX.
– D.W.
Apr 1 at 18:48
• 1. No, I'm not the one who asks the question 2. for image since I use the color to correspond to figure information, I don't think it's convienet for me to transcribe text, or you can do it, and I will delete the answer if someone transcribes to txt 3. All answers are not perfect, and I think I point out why it's didn't totally right, I think others can just see it as reference but not the correct answer. Apr 15 at 0:50