Rectangles overlap

Question

“Rectangles” A rectangle can be specified in a 2-dimensional plane using the top left (north west) point and the bottom right (south east) point.  Given n rectangles (using 2 points each), give an O(n log n) algorithm that tells if any two rectangles from the list overlap.  Two rectangles are said to overlap, if there is a common point in both of them.  [If a rectangle is entirely contained in another, they are still said to “overlap”, even though their lines don’t cross.]

How to solve this problem?

Answer 1

One D&C way that works in practice very well, but is not perfect, is as follows:

Pick a dividing median line (by taking a median of all the center points x values of all the rectangles).  [The dividing median is a line parallel to y-axis.]

Divide the rectangles into 3 subsets:

Left - rectangles that are entirely to the left of dividing median  // n1

Center - rectangles that overlap with the dividing median // n2

Right - rectangles that are entirely to the right of the dividing median. // n3

Obviously, the rectangles in Left and in Right can not overlap.

And the rectangles in Center already overlap along the x-axis, now we can simply check if they overlap along the y-axis.  This can be done in O(n log n) as follows: Simply sort the rectangles (line intervals) in terms of y-axis.  Iterate the list and compare the neighbors.  Now, we observe that this can be done in O(n) time, if the rectangles are pre-sorted in terms of their y-axis once at the very beginning.

So, the recurrence relation basically becomes:

T(n) = O(n) + T(n1 + n2) + T(n2 + n3) + O(n2), where n1 + n2 + n3 is n.

If n2 is not too large, then this becomes O(n log n) algorithm.

If n2 is large, then the center part is pretty big, and we are likely to find an overlap there among center parts already.

So, this method is not guaranteed to be O(n log n), but it works in practice.  For a cleverer algorithm, think of breaking the original set into 5 subsets on the basis of a central rectangle.

Comments

Hi professor, it may have a case that the left/right part overlaps with center part, thus we can't solve it with only 3 part. Here is an algorithm, which divides rectangles into 5 parts. I think it works. https://algnotes.wordpress.com/2015/05/20/intersection-of-rectangles/

---

Taoran, yes - the left and right can overlap with the central part.  That is the reason we need to include central with both left, and right.  That is what leads to T(n1+n2) and T(n2+n3) recursive calls.  In practice, n2 is not too big every time, so the algorithm works in O(n log n) time in practice.

Yes, the algorithm that breaks into 5 parts is more evolved and I give a hint at the bottom along those lines.

---

Hi professor, sorry for miss the point. But for example, There are 4 rectangles where three have same x-coordinate but they don't overlap, while one lays left and overlaps with one of them. When we call the recursive method, f({left_1}+{center_1, center_2, center_3}) will infinitely call f({left_1}+{center_1, center_2, center_3}). So we can't get the answer.

---

Taoran, you are absolutely right. The algorithm is not perfect.  For small values of n, we need to use the base case of recursion and do a brute force portion (O(n^2) time).  For larger values of n, we can have a non trivial partition.

Answer 2

I can give you a hint, but its not based on Branch and Bound as you catalogued this question.

You shall try Interval Tree Structure, which is similar with Binary Search Tree. The difference is the way it to insert node and search. And for the rectangle overlap scenario, you can consider each rectangle as two points, leftUp and rightBottom, which can construct X side and Y side of rectangle. 

The rule we determine whether two rectangles overlapped is: Rectangle A's X side does not intersect with Rectangle B's X side && Rectangle A's Y side does not intersect with Rectangle B's Y side, which is what Interval Tree Structure can do.

Answer 3

To have two rectangles overlaping, the [x1left, x1right] and [x2left, x2right] must be overlaping, and [y1low,y1high], [y2low,y2high]must be overlaping.

Sort all x values of all points, and all y values of all points.

interate through all x values, when see the left top value appear, put it in a set, when see the right bottom value, remove it from the set. When you read a point from another rectangle from xi when the set is not empty, it is overlapping in x axis with all rectangles with points in the set at the time. Record these pairs.

Do the same for v values. (we can ignore values did not appear in any of the pairs in the x scan above to save time).

Overlapping rectangles would appear as pairs in both x and y.

Running time is O(n log n) if these are few overlapping(dominated by sorting).

Worst case would be O(n^2) if every rectangles is overlapping with every others(dominated by adding pairs).

Answer 4

https://algnotes.wordpress.com/2015/05/20/intersection-of-rectangles/