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?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ from line in 1D, do you mean for a line you store [start,end] like [2,4] ? $\endgroup$– Ashish NegiOct 30, 2013 at 9:45
-
$\begingroup$ @AshishNegi [start,weight] like [9,4] $\endgroup$– Ilya GazmanOct 30, 2013 at 9:50
-
$\begingroup$ what do you mean by weight ? is it like end = start + weight ? $\endgroup$– Ashish NegiOct 30, 2013 at 9:53
-
2$\begingroup$ Interval trees should do that for you. $\endgroup$– G. BachOct 30, 2013 at 10:02
-
1$\begingroup$ your full answer is on wikipedia. Also, there are many lecture notes about interval stabbing problem. $\endgroup$– ParhamOct 30, 2013 at 12:16
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
See also interval trees, which have similar properties.
