Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have two time intervals A and B that occur in time at a start time and occur until an end time. These time intervals however repeat in time from their start time until another end time.

So each interval starts at a specific instant in time, 'occurs' for a duration of time, then repeats after a duration (period) of time.

Interval A

  • Start: 1s
  • End: 5s
  • Repeat Until: 50s
  • Repeat Period: 10s

      |-[xxx]-----[xxx]-----[xxx]-----[xxx]-----[xxx]----|
    

Interval B

  • Start: 7s
  • End: 10s
  • Repeat Until: 50s
  • Repeat period: 9s

      |-------[xx]-----[xx]-----[xx]-----[xx]-----[xx]---|
    

Timeline

A:|-[xxx]-----[xxx]-----[xxx]-----[xxx]-----[xxx]----|
B:|-------[xx]-----[xx]-----[xx]-----[xx]-----[xx]---|

If these were considered linear (which they are partially - except for the duration) I could just set two equations equal to each other to figure out when they conflict.

|-x---x---x---x---x---x---x---x---x---x---x---x---x|

event.start + event.period(num of repeats) = new event.start
other.start + other.period(num of repeats) = new other.start

Set equal to each other solve for num of repeats

However I'm only dealing with integers, I'm checking for overlap not an exact point in time, and it doesn't tell me when other intervals overlap. I'm lost.

Representing these intervals so that I can calculate when they overlap and for how long is really the bottom line. I'm missing an important concept here that I can't quite get, some thoughts included series, regression, and brute force (calculate every position manually) but I'm lost without a clear understanding of math to help me forward.

share|improve this question
    
Ar eyou only interested in cases of two intervals at a time? Or do you need an algorithm that is efficient for detecting collisions between many intervals, or many pairs of intervals? And are the numbers in your examples typical? Or are the numbers in your actual application much larger? –  MJD Nov 28 '13 at 15:18
    
Thanks for the edits - There are multiple intervals, I could potentially compare pairs. And no the numbers are as you said much bigger but I'm not sure that makes a difference (I could apply by units instead - years, months, days, hours, minutes, seconds, miliseconds) Time gets really confusing... –  Nate Nov 28 '13 at 15:28
    
And I'm not sure what you want the output of your algorithm to be. Is it just a true or false value that indicates whether the input intervals overlap? Or is it some sort of description of when the overlaps occur? And if the latter, does the description have to be another interval in the same format? Or could it be some other sort of structure? (You might answer this by editing your question instead of trying to squeeze the answer into a comment.) –  MJD Nov 28 '13 at 15:30
    
Also I find your diagram confusing. It seems to me that structure $A$ indicates that something is active for 4 seconds out of every 10, but the diagram shows either 3 or 5 boxes checked. I think $A$ means that some even occurs from $t=1$ until $t=5$, from $t=11$ until $t=15$, and then similarly from $21$ until $25$, from $31$ until $35$, from $41$ until $45$, and then never occurs again. Is that correct? –  MJD Nov 28 '13 at 15:33
    
The latter - 'description' when the next overlap starts/ends –  Nate Nov 28 '13 at 15:45
show 1 more comment

2 Answers

I could not think of a definite answer but this approach might help...

Code the two sequences in binary with the intervals being '+1' and repetition periods being '0's. Get the dot product of the two binary sequences. The number of '1's will give you the total duration of overlap. Also the number of overlaps can be obtained by counting the number of uninterrupted sequences of '1's

If the repeat until duration of one signal is smaller than the other pad the smaller one with zeros at the end.

Hope you get the idea.

share|improve this answer
    
I thought of something very similar but without bit masks I'm just afraid that my domain set becomes too large... –  Nate Nov 29 '13 at 23:17
add comment

You would like to know which integers satisfy two conditions:

  • $t \equiv 1,2,3,4,5\; (\,mod \,10\,)$
  • $t \equiv 7,8,9,10\; (\,mod \,9\,)$

Since you're a programmer you may want to think of this as

  • t % 10 in [1,2,3,4,5]
  • t % 9 in [0,1,7,8]

Since 9 and 10 are relatively prime, we can always find numbers which satisfy congruence conditions mod 9 and mod 10 by the Chinese Remainder Theorem.


Let's focus on solving the equation $ t \equiv a\; \text{mod}\;m$ and $ t \equiv b\; \text{mod}\;n$ with $m,n$ relatively prime. In fact, $10-9=1$ so we are good.

Using the Euclidean algorithm, we can efficiently find two numbers two numbers $a_0, b_0 \in \mathbb{Z}$ such that $ma_0 + nb_0 = 1$. This means $$ b_0 n \equiv 1\; \text{mod}\;m \hspace{0.25in}\text{&}\hspace{0.25in}a_0 m \equiv 1\; \text{mod}\;n$$

So $t = ab_0 n + a_0 b m$ satisfies both congruences.


In our case, $10-9=1$ so that $1(-9)+3(10)= 21 $ satisfies $21\equiv 1 \; \text{mod}\;10$ and $21\equiv 3 \; \text{mod}\;9$. Since your intervals are of length 4 and 5, there are 20 possible overlap times you have to watch out for.

share|improve this answer
    
I think your on the right track but not sure where '[0, 1, 7, 8]' came from... or what the diagrams mean? Thanks for the help! –  Nate Nov 24 '13 at 17:35
    
The other questions this imposes is when and where... I don't necessarily want to run through all times t from 0 to upper bound (if there even is one) –  Nate Nov 24 '13 at 20:14
    
that is an interesting question. how do we "efficiently" find solutions to M different congruence conditions? –  john mangual Nov 25 '13 at 11:49
    
Indeed I really don't want to be 'guess checking' :) –  Nate Nov 26 '13 at 20:54
    
I'm going to look into this a little more before I accept but you deserve the bounty! –  Nate Nov 29 '13 at 23:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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