# Lines intersections with a point in 1D

I have an array of lines in 1D represented by coordination and weight, it can be only positive weight. I want to find all the lines that intersect a point in a given range.

Is there any efficient way of doing it?

• from line in 1D, do you mean for a line you store [start,end] like [2,4] ? – Ashish Negi Oct 30 '13 at 9:45
• @AshishNegi [start,weight] like [9,4] – Ilya Gazman Oct 30 '13 at 9:50
• what do you mean by weight ? is it like end = start + weight ? – Ashish Negi Oct 30 '13 at 9:53
• Interval trees should do that for you. – G. Bach Oct 30 '13 at 10:02
• your full answer is on wikipedia. Also, there are many lecture notes about interval stabbing problem. – Parham Oct 30 '13 at 12:16

You can do the trivial scan in $\mathcal{O}(n)$ time where $n$ is the number of intervals (just check for each interval whether your value is in it) or you can use an interval tree; those allow for querying in logarithmic time, see for example here.
If you store all of the intervals in a segment tree, then the operation "find all intervals that contain the point $x$" is known as a stabbing query. Building a segment tree from $n$ intervals takes $O(n \lg n)$ time, but once it is built, you can answer a stabbing query in $O(\lg n + k)$ time, where $k$ is the number of intervals that intersect the point $x$ (i.e., the length of the output of the operation).
In comparison, a linear scan (as described in G. Bach's answer) requires no preprocessing but takes $O(n)$ time to answer each stabbing query. Thus, if you plan to make many stabbing queries on the same set of intervals, it may be faster to build a segment tree in advance, as each stabbing query can then be answered much faster.