Comparing overlapping ranges

Question

I'm going to ask this question using Scala syntax, even though the question is really language independent.

Suppose I have two lists

val groundtruth:List[Range]
val testresult:List[Range]

And I want to find all of the elements of testresult that overlap some element in groundtruth.

I can do this as follows:

def overlaps(x:Range,y:Range) = (x contains y.start) || (y contains x.start)
val result = testresult.filter{ tr => groundtruth.exists{gt => overlaps(gt,tr)}}

But this takes O(testresult.size * groundtruth.size) time to run.

Is there a faster algorithm for computing this result, or a data structure that can make the exists test more efficient?

---

P.S. The algorithm should work on groundtruth and testresult generated with an expression like the following. In other words, there are no guarantees about the relationships between the ranges within a list, the Ranges have an average size of 100 or larger.

(1 to 1000).map{x =>
   val midPt = r.nextInt(100000);
   ((midPt - r.nextInt(100)) to (midPt + r.nextInt(100)));
}.toList

Answer 1

Try an interval tree. Cormen, Leiserson, Rivest and Stein discuss these in (IIRC) chapter 14.

Alternatively, if your lists of intervals are both sorted and the intervals within a list are non-overlapping, then the following algorithm solves your problem in linear time and in a single pass over both lists:

(define interval cons)
(define lower car)
(define upper cdr)

(define (overlap a b)
  (cond ((or (null? a) (null? b)) '())
        ((< (upper a) (lower b))
         (overlap (cdr a) b))
        ((> (lower a) (upper b))
         (overlap a (cdr b)))
        (#t  ;; (car a) and (car b) overlap
             ;; EDIT: there's a bug in the following part.
             ;; The code shouldn't skip over both cars at once,
             ;; since they may also overlap with further intervals.
             ;; However, I'm too tired to fix this now.
         (cons (interval (max (lower a) (lower b))
                         (min (upper a) (upper b)))
               (overlap a b)))))

(I hope you can read Scheme :)

Answer 2

If groundtruth were stored in a hashed set, checking the presence of members of test result in it would be O(n).

Edit: I didn't realise you were working solely with ranges represented by their endpoints. D'oh!

Some sort of tree-based structure has got to be your best bet.

Answer 3

If you could sort the groundtruth list by range beginning value, then for each range in testresult you can do a binary search to get the subset of ranges whose low bound is less than or equal to the range in question. Then you need to sequentially search that subset for those whose high bound is greater than or equal to the high bound of the range you're testing.

The worst case is still O(n^2), since it's possible that all of the groundtruth ranges would have a low bound that meets the criteria, but the run time with actual data would likely be much less.