MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
djmp at earthlink.net
http://home.earthlink.net/~djmp/



  • Prev by Date: Start Debugger for MathLink from Mathematica
  • Next by Date: Re: Sorting problem
  • Previous by thread: Re: checking for overlap
  • Next by thread: RE: checking for overlap