1
$\begingroup$

Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair?

The naive approach is very straightforward, but has O(intervals) test performance:

list intervals (min, max)

func testVal(val){
  foreach (interval(min, max) in intervals)
    if (val > max) || (val < min) return false      
  return true
}

In the problem I'm facing the list is not updated frequently, but it is tested against with very high frequency.

Thus, it's acceptable for updating the list to be expensive, but tests need to be sublinear, ideally constant time.

One option is to insert every value in the intervals into a hashtable, but this is memory-intensive and not practical when the intervals get large. Memory usage needs to be proportional to the number of intervals, not the sum of the sizes of the intervals (probably ok to have a log(n) memory usage term thrown in if it greatly aids performance).

I've started poking around with various tree-based options to make this better, but it feels like a general enough problem that I suspect there is preexisting work I should be referencing. Are there any existing solutions to get sublinear tests (ideally constant time) on a list of intervals by preprocessing them into some other datastructure(s)?

$\endgroup$
2
  • $\begingroup$ Does this answer answer your question? You can also search for "segment tree" or "interval tree". $\endgroup$
    – John L.
    Feb 26, 2019 at 20:07
  • $\begingroup$ Those are better than the naive approach, but they're solving the problem of identifying a specific containing interval. I'm hoping it can be done even cheaper (perhaps constant time) if you're just performing a membership test. $\endgroup$ Feb 26, 2019 at 20:14

2 Answers 2

1
$\begingroup$

You need an interval tree, which queries in O (logn + m) time, where $m$ is the number of intervals the point hits (as opposed to O (n) for n intervals in the data structure).

This should produce enough savings that you'll hardly notice the cost of $m$.

This output sensitive algorithm is likely the best you can do. The other answer suggests this structure without name, with the additional step of making all intervals disjoint to get log$n$ ($m$ guaranteed to be 1) That's fine, but I'd still use an established data structure.

$\endgroup$
1
$\begingroup$

Here's my thought process on this problem:

  • If you only care about "in or out", you can reduce the list of intervals so that no intervals overlap, and the intervals are in sorted order.
    • Sorting by leftmost point takes $O(n \log n)$, then replacing any overlapping pairs with their union takes $O(n)$. But you've said you don't care how long this part takes.
  • For a given point and a given interval, you can determine whether the point is "outside to the left", "inside", or "outside to the right" in $O(1)$.
    • This assumption only works as long as you have a fixed word length, but that's generally true for all practical purposes.
    • Let's change the terms: "outside to the left" is "less than", "inside" is "equal to", and "outside to the right" is "greater than".
  • Now you can use standard binary search!
    • Since each comparison is $O(1)$, the total time is $O(\log n)$.

And voilà, each check takes only logarithmic time! Setting up the list in the first place takes $O(n \log n)$, and adding a new interval to the list later takes $O(n)$ in the worst case.

$\endgroup$
3
  • $\begingroup$ Numbers are not $O(1)$ bits long. Rather, we’re using the unit cost word RAM model when analyzing algorithms. $\endgroup$ Feb 26, 2019 at 21:10
  • $\begingroup$ @YuvalFilmus Aren't those equivalent? We're saying we can bound the cost of operations on numbers because we can bound the size of the numbers by the constant size of the machine word. $\endgroup$
    – Draconis
    Feb 26, 2019 at 22:16
  • $\begingroup$ You should measure your numbers in words rather than in bits. $\endgroup$ Feb 27, 2019 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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