0
$\begingroup$

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?

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

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.