How to tell if two intervals intersect

Suppose we have two half-open intervals

[A, B) [X, Y)

and we want to know whether they intersect. In any particular case, it's obvious. For example

[1, 2) [3, 4)	disjoint
[1, 5) [3, 4)	intersect

But can we write a rule that covers the general case? Let's see...the first interval could contain the second, or it could overlap on the left, or on the right, or...this is getting complicated...

Here's how to do it.

There are 24 permutations of the 4 endpoints, but only 6 satisfy the conditions A < B and X < Y. These are

A B X Y
A X B Y  intersect
A X Y B  intersect
X A B Y  intersect
X A Y B  intersect
X Y A B

The four in the middle intersect, and the two on the ends do not.

The first is identified by B <= X, a condition that holds for it and no other, and the last is identified by Y <= A, a condition that holds for it and no other. Both comparison have an open bound on the left and a closed bound on the right, so a <= comparison is appropriate.

We can identify the four intersecting cases with the condition

NOT (B <= X OR Y <= A)

or, distributing the NOT

X < B AND A < Y

Steven W. McDougall / resume / swmcd@theworld.com / 2009 November 21