Re: checking for overlap

• To: mathgroup at smc.vnet.net
• Subject: [mg20098] Re: [mg20065] checking for overlap
• From: "David Park" <djmp at earthlink.net>
• Date: Thu, 30 Sep 1999 02:43:10 -0400
• Sender: owner-wri-mathgroup at wolfram.com

>I am looking for an elegant way of checking for overlap.
>
>Suppose I have a set of time intervals given by
>ints = {{t1,t2},{t3,t4},{t5,t6}. ...} and another set of times
>tvals = {u1,u2,u3, ...}.
> What is a fast, elegant way of checking which of the tvals is within any of
>the ints time intervals?
>
>Thanks,
>Dennis
>
>

Dennis,

Perhaps I should know better than to touch these kinds of problems, but here is my
try. You will probably get some better methods from the real mathematicians in
MathGroup.

Here is a test case.

ints = Table[{2n, 2n + 1}, {n, 0, 4}];

Create ints2 by applying Interval to ints.

ints2 = Interval @@ ints
Interval[{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}]

Here is a random set of tvals.

tvals = Table[Random[Real, {0, 10}], {10}]
{7.28844, 7.97387, 1.4635, 8.27075, 4.35604, 0.938894, 6.27754, 3.95451, 4.18765,
3.76676}

It is not clear whether you just want True or False answers for each value, want a
list of the positions, or want to select out the values. This selects the values that
lie in the intervals.

Select[tvals, IntervalMemberQ[ints2, #] &]
{8.27075, 4.35604, 0.938894, 6.27754, 4.18765}

Here is the timing for a longer case on a 166 Mh Pentium. 100 values with 50
intervals.

ints2 = Interval @@ Table[{2n, 2n + 1}, {n, 0, 49}];
tvals = Table[Random[Real, {0, 100}], {1000}];
Select[tvals, IntervalMemberQ[ints2, #] &]; // Timing
{1.32 Second, Null}

The timing appears to be linear with the number of tvals and the number of intervals.

David Park