66

Say [a,b] represents the interval on the real line from a to b, a < b, inclusive (ie, [a,b] = set of all x such that a<=x<=b). Also, say [a,b] and [c,d] are 'overlapping' if they share any x such that x is in both [a,b] and [c,d].

Given a list of intervals, ([x1,y1],[x2,y2],...), what is the most efficient way to find all such intervals that overlap with [x,y]?

Obviously, I can try each and get it in O(n). But I was wondering if I could sort the list of intervals in some clever way, I could find /one/ overlapping item in O(log N) via a binary search, and then 'look around' from that position in the list to find all overlapping intervals. However, how do I sort intervals such that such a strategy would work?

Note that there may be overlaps between elements in the list items itself, which is what makes this hard.

I've tried it by sorting intervals by their left end, right end, middle, but none seem to lead to an exhaustive search.

Help?

cespinoza
  • 1,437
  • 1
  • 12
  • 18

6 Answers6

64

For completeness' sake, I'd like to add that there is a well-known data structure for just this sort of problem, known (surprise, surprise) as an interval tree. It's basically an augmented balanced tree (red-black, AVL, your pick) that stores intervals sorted by their left (low) endpoint. The augmentation is that each node stores the largest right (high) endpoint in its subtree. This tree allows you to find all overlapping intervals in O(log n) time.

It's described in CLRS 14.3.

warvariuc
  • 57,116
  • 41
  • 173
  • 227
Ben
  • 6,023
  • 1
  • 25
  • 40
27

[a, b] overlaps with [x, y] iff b > x and a < y. Sorting intervals by their first elements gives you intervals matching the first condition in log time. Sorting intervals by their last elements gives you intervals matching the second condition in log time. Take the intersections of the resulting sets.

gdj
  • 1,295
  • 10
  • 10
  • 1
    Wouldn't the intersection take O(n) time though? If the list were N elements long, a query interval of 'similar size' to those in the list would yield m matches in the first list and up to N-m matches in the second list, and taken the intersection would require traversing all N elements, wouldn't it? – cespinoza Dec 15 '10 at 04:53
  • It'd take O(the size of the smaller list of items matching the condition). If a small fraction of all intervals match, say f(N), it'd take O(f(N)). I assumed that would be the case—otherwise I think any strategy would be roughly O(N). – gdj Dec 15 '10 at 14:33
  • 23
    This is not the best answer; what you have described here falls under the "Naive approach" on this page: http://en.wikipedia.org/wiki/Interval_tree. Indeed the other answer more correctly suggests looking into interval trees. – johnbakers Jun 18 '13 at 12:33
  • 4
    Overlap detection condition requires >= and <=. Above answer has same runtime as brute force (i.e. O(n)). Interval trees described in Corman Sec 14.3 is what you want. – Shital Shah Aug 01 '14 at 08:54
  • @gdj why would it take `O(the size of the smaller list of items matching the condition)`? Shouldn't it be `O(the size of the *larger* list of items matching the condition)`? Don't you need to go through both sets to take the intersection? – max Jun 23 '17 at 13:59
  • 1
    @max: iterate through the smaller set; for each element, check if it is in the larger set (using something like a hashtable for constant membership queries). – Tom Church Jul 30 '17 at 04:56
4

A 'quadtree' is a data structure often used to improve the efficiency of collision detection in 2 dimensions.

I think you could come up with a similar 1-d structure. This would require some pre-computation but should result in O(log N) performance.

Basically you start with a root 'node' that covers all possible intervals, and when adding a node to the tree, you decide if it falls on the left or the right of the midpoint. If it crosses the mid point, you break it into two intervals (but record the original parent) and recursively proceed from there. You can set a limit on the depth of the tree, which can save memory and improve performance, but comes at the expense of complicating things a little (you need to store a list of intervals in your nodes).

Then when checking an interval, you basically find all leaf nodes that it would be inserted into were it inserted, check the partial intervals within those nodes for intersection, and then report the interval that is recorded against them as the 'original' parent.

sje397
  • 41,293
  • 8
  • 87
  • 103
  • 5
    That similar structure, oddly enough, is called a binary tree. – Engineer Mar 13 '12 at 19:51
  • 1
    @Nick Wiggill - It's a type of binary tree, sure, but there are a lot of uses for binary trees and the algorithm I'm describing is a little more detailed. – sje397 Mar 14 '12 at 23:26
1

Just a quick thought 'off the cuff' so to speak.

Could you organize them into 2 lists, one for start of intervals and the other for end of intervals.

This way, you can compare y to the items in the start of interval list (say by binary search) to cut down the candidates based on that.

You can then compare x to the items in the end of interval list.

EDIT

Case: Once Off

If you are comparing only single interval to the list of intervals in a once-off situation, I don't believe sorting will help you out since ideal sorting is O(n).

By doing a linear search through all x's to trim out any impossible intervals then doing another linear search through the remaining y's you can reduce your total work. While this is still O(n), without this you would be doing 2n comparisons, whereas on average, you would only do (3n-1)/2 comparisons this way.

I believe this is the best you can do for an unsorted list.

Case: Pre-sorting doesn't count

In the case where you will be repeatedly comparing single intervals to this list of intervals and your pre-sort your list, you can achieve better results. The process above still applies, but by doing a binary search on the first list then the second you can get O(m log n) as opposed to O(mn), where m is the number of single intervals being compared. Note, still still gives you the advantage of reducing total comparisons. [2m log n compared to m(3(log n) - 1)/2]

Dan McGrath
  • 41,220
  • 11
  • 99
  • 130
  • Your initial suggestion at the top of your answer falls under the "Naive approach" on this page: en.wikipedia.org/wiki/Interval_tree. – johnbakers Jun 18 '13 at 12:42
0

You could sort by both left end and right end at the same time and use both lists to eliminate none overlapping values. If the list is sorted by the left end then none of the intervals to the right of the right end of the test range can overlap. If the list is sorted by the right end then none of the intervals to the left of the left end of the test range can overlap.

For example if the intervals are

[1,4], [3,6], [4,5], [2,8], [5,7], [1,2], [2,2.5]

and you're finding overlap with [3,4] then sorting by left end and marking position of the right end of the test (with the right end as just greater than its value so that 4 is included in the range)

[1,4], [1,2], [2,2.5], [2,8], [3,6], [4,5], *, [5,7]

you know [5,7] can't overlap, then sorting by right end and marking position of the left end of the test

[1,2], [2,2.5], *, [1,4], [4,5], [3,6], [5,7], [2,8]

you know [1,2] and [2,2.5] can't overlap

Not sure how efficient this would be since you're having to do two sorts and searches.

Nemo157
  • 3,559
  • 19
  • 27
0

As you can see in other answers, most algorithms come together with a special data structure. For example, for unsorted list of intervals as input O(n) is best that you'll get. (And usually it's easier to think in terms of data structure that dictates the algorithm).

In this case, your question is not complete:

  • Are you given the whole list or it is you who actually creates it?

  • Do you have to perform just one such lookup or many of them?

  • Do you have any estimations for operations it should support and their frequencies?

For example, if you have to perform just one such lookup, then it's not worthy to sort the list before. If many, then the more expensive sorting or generation of an "1D quadtree" would be amortized.

However, it would be difficult to solve it, because a simple quadtree (as I understand it) is able just to detect the collistion, but it's not able to create the list of all the segments that are overlapping with your input.

One simple implementation would be an ordered (by coordonate) list where you insert all the segment ends with flag start/end and with segment number. In this way, by parsing it (still O(n), but I doubt you can make it faster if you also need the list of all the segments that overlaps), and keeping the track of all opened segments that were not closed at "check points".

ruslik
  • 14,714
  • 1
  • 39
  • 40