Thread Subject:

Find indices where overlapping intervals occurs

Hello!
Im having a problem getting the indices (integers) from overlapping intervals. Let me explain:

let's say for instance that I have some intervals belonging to say

set A:
[1,3]
[5,8]
[11,12]

set B:
[4,6]
[8,10]

The indices(integers), where the intervals of set A overlaps with intervals of set B could easily be found by using the matlab "intersect" function after constructing the intervalls to vectors. Now this is not an option to me due to my intervals could hold a couple of hundred millions elements (integers) if made to vectors, so i just have to work with the the start and end values for each intervall. I should mention that all my intervals are closed intervals and positive integers. I have tried to use nestled loops but get lost in translation such of speech... Im wondering if there exists some solution (maybe mathematical formula) to find the indices(integers) where intervals overlaps based only on the start and end values.

Best regards

Teo

"Theodor Zouk" <rebet4@hotmail.com> wrote in message <j8o7c9$m9m$1@newscl01ah.mathworks.com>...
> Hello!
> Im having a problem getting the indices (integers) from overlapping intervals. Let me explain:
>
> let's say for instance that I have some intervals belonging to say
>
> set A:
> [1,3]
> [5,8]
> [11,12]
>
> set B:
> [4,6]
> [8,10]
>
...... Im wondering if there exists some solution (maybe mathematical formula) to find the indices(integers) where intervals overlaps based only on the start and end values.
- - - - - - - - - -
 If the numbers of intervals in each set are not large or if time of execution is not important, you could always use the "brute" force method of comparing each interval of one set with each interval of the second set. If each of the two sets of intervals consist of mutually disjoint intervals, then the results of this procedure would also have disjoint intervals. Each individual test might look something like this. Let [a,b] be an interval in set A and [c,d] an interval in B. Whenever max(a,c) <= min(b,d) then add [max(a,c),min(b,d)] to the list of common starting and stopping "indices". Either way, move on to the next pair.

  If each set has mutually disjoint intervals and these have been arranged in ascending order in each set (as in your example,) you could do a kind of "merge", commencing at the beginning of each set, in which a pair of intervals from the two respective sets are "compared". If by the test in the first paragraph above there is a non-empty intersection, add it to your list. Whether or not there is such an intersection, you advance to the next interval of the set that had the smallest upper bound. The resulting list will also have disjoint, ascending intervals. This procedure would presumably be much faster than the brute force method above.

Roger Stafford

"Roger Stafford" wrote in message <j8putc$rn0$1@newscl01ah.mathworks.com>...
> "Theodor Zouk" <rebet4@hotmail.com> wrote in message <j8o7c9$m9m$1@newscl01ah.mathworks.com>...
> > Hello!
> > Im having a problem getting the indices (integers) from overlapping intervals. Let me explain:
> >
> > let's say for instance that I have some intervals belonging to say
> >
> > set A:
> > [1,3]
> > [5,8]
> > [11,12]
> >
> > set B:
> > [4,6]
> > [8,10]
> >
> ...... Im wondering if there exists some solution (maybe mathematical formula) to find the indices(integers) where intervals overlaps based only on the start and end values.
> - - - - - - - - - -
> If the numbers of intervals in each set are not large or if time of execution is not important, you could always use the "brute" force method of comparing each interval of one set with each interval of the second set. If each of the two sets of intervals consist of mutually disjoint intervals, then the results of this procedure would also have disjoint intervals. Each individual test might look something like this. Let [a,b] be an interval in set A and [c,d] an interval in B. Whenever max(a,c) <= min(b,d) then add [max(a,c),min(b,d)] to the list of common starting and stopping "indices". Either way, move on to the next pair.
>
> If each set has mutually disjoint intervals and these have been arranged in ascending order in each set (as in your example,) you could do a kind of "merge", commencing at the beginning of each set, in which a pair of intervals from the two respective sets are "compared". If by the test in the first paragraph above there is a non-empty intersection, add it to your list. Whether or not there is such an intersection, you advance to the next interval of the set that had the smallest upper bound. The resulting list will also have disjoint, ascending intervals. This procedure would presumably be much faster than the brute force method above.
>
> Roger Stafford


Thank you for your answer. Im using a kind of a brute force method and it works fine and the time of execution is relative low.
Thanks again

/Theodor