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

Question

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.

• D.W.: You refer to a query point, but I don't see any query point in the statement of the problem.
• Hagen von Eitzen: Line segments in $\Bbb R^2$?
• TilmannZ: Did you have a look at cs.stackexchange.com/questions/120384/… (if you consider your line a 'shape') and cs.stackexchange.com/questions/117333/… (if you consider lines as bounding boxes).
• HEKTO: Please also see my answer here: cs.stackexchange.com/questions/123349/…
• user16034: The duals of the line segments are those wedges and the dual of the line is a single point. So you have to construct the arrangement of lines generated by the wedges and from this, point location in that planar subdivision. Nothing really appetizing...

Answer 1

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.

enter image description here

enter image description here

enter image description here

• Yuval Filmus: Are you the one who asked the original question?
• Yuval Filmus: It is a bit problematic to add an answer which you know is (slightly) wrong, without at least pointing out potential problems in it.
• D.W.: 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.
• Zhang Kin: 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.
• Kenneth Kho: I upvoted as this seems to be a useful partial answer. According to the teacher part (a) and (b) are correct and part (c) is incorrect.