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

• You refer to a query point, but I don't see any query point in the statement of the problem.
– D.W.
Mar 21, 2020 at 16:03
• Line segments in $\Bbb R^2$? Mar 21, 2020 at 19:47
• 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). Mar 22, 2020 at 14:05
• Please also see my answer here: cs.stackexchange.com/questions/123349/… Jun 2, 2020 at 21:53
• 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...
– user16034
Jun 27, 2023 at 14:39