Finding all the intervals that does not overlap with the point

2
votes

I have intervals of the form (a1, b1), (a2, b2), ...., (an, bn).
I would like to support the following operations

  1. Adding a new interval.
  2. Deleting an existing interval.
  3. Given a point, find all intervals that do not overlap with the point.

Intervals tree is the straightforward solution if we want to find intervals which overlap with the point. What about the case when we want to find non intersecting intervals?

1
algorithmcomputational-geometry
What do "add" and "delete" exactly mean? Should adding (2,4) to (1,3) produce (1,3),(2,4) or (1,4)? – Oriol
@Oriol - think it should be (1,3),(2,4) – shapiro yaacov
You can insert in the tree the complementaries of the intervals: instead of [a,b], insert [-inf,a] and [b,+inf]. Make sure to keep the identity of the original intervals. – Yves Daoust

1 Answers

3
votes

Have all nodes in two trees simultaneously. Tree A holds them by key ai and tree B holds them by key bi.
Insertion and deletion is obviously O(log n).
For requirement 3, print the nodes in B from the smallest to the biggest and stop when bi is still smaller then the point. Same, but backwards, in A.

Example:
Given (1,10), (5,18), (13,20), and a point 12.
The interval(s) in A where ai is bigger than 12 is (13,20), and in B the interval(s) that are smaller are (1,10).