In case anyone is into this sort of thing
I have two intervals, (A1,B1] and (A2,B2]--the intervals include B1 and B2 respectively, but not A1 and A2. B1 >= A1, and B2 >= A2.
What's the quickest way to check to see if the two intervals overlap? Specifically, assume that the intervals don't overlap very often.
I ended up working this out backwards, getting the case that is optimal when the intervals overlap more often than not, but it's a simple transformation to go back and forth (say the man's name if you know it!)
posted by Lemming @ 10/25/2005 10:55:00 AM
4 comments
4 Comments:
I got it down to four comparisons and three boolean operators, just working from basics. Dunno if there's some fancier way of doing it.
The intervals overlap if:
(A1 <= A2 and A2 < B1) or (A2 <= A1 and A1 < B2)
Proof:
Assuming no two points are equal (for now), there are four ways the intervals can overlap: (The A1-B1 interval is represented by < >, and the A2-B2 interval by { })
A1 A2 B1 B2 < { > }
A1 A2 B2 B1 < { } >
A2 A1 B2 B1 { < } >
A2 A1 B1 B2 { < > }
Non-overlaps are:
A1 B1 A2 B2 < > { }
A2 B2 A1 B1 { } < >
So if either A1 or A2 is second in the ordering (alternately, if B1 or B2 is third), there is an overlap. Expressed differently, if Ax is first, the other A must come before Bx. Thus there is overlap if:
A1 < A2 < B1 or
A2 < A1 < B2
Now to consider the cases where some points are equal. If only A1 = A2, (ie, A1 != B1 and A2 != B2), there's still overlap, since by definition A1 <= B1 and A2 <= B2, either A1 <= A2 < B1 or A2 <= A1 < B2 will hold. (This made a lot more sense when I worked it out visually.)
But if A1 = B2 or A2 = B1, there's not overlap, because the point is included in one interval but not the other. (Worded differently, the two form a continuous interval (A1,B2] or (A2,B1], depending.) So the true condition must be
A1 <= A2 < B1 or
A2 <= A1 < B2
which boils down to seven operations.
Yes, I know all I proved is that this solution works, not that it's optimal. Partial credit?
Partial credit it is!
You can do the fail-fast in two comparisons and one boolean operator (which is typically a short-circuit operator, hence the fail-fast), and you can do the opposite in two comparisons and two boolean operators (well, one, but two if you want to take advantage of short-circuit operators).
In case I'm confusing you, the "short-circuit" refers to the usual case of using && or || in C/C++ (or most any other language). If the first operand to && evaluates to "false", the second isn't looked at at all.
In the case of the optimal solution, only one comparision occurs in the fail-fast case.
Assuming that the intervals overlap with a "very small" probability, you can fail-fast on half of the cases, using 1.5 comparisions and 1 boolean operator on average.
Also, you've reminded me of my wish that some languages would include ternary comparison operators. Not sure how to do that in an umambiguous fashion, however.
Post a Comment
<< Home