Question

link, MIT handouts Person_A

Describe an algorithm that takes an unsorted array of axis-aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair.

Axis-aligned means that all the rectangle sides are either parallel or perpendicular to the x- and y-axis.

Each rectangle object has two variables: the x-y coordinates of the upper-left corner and the bottom-right corner.

Analysis

A lot of different solutions on the internet, example 1 and example 2, and some questions asks you to return all overlapping pairs. For now, we just return any pair that overlaps.

Solution

I concluded some solution and come up with this (the idea of BST is covered in the end of this pdf):

1. Sort the input by left edge.
2. One by one, get one rectangle from the sorted input, and make a pair (rect.top, rect.bottom).
3. Insert this pair into a Interval Search Tree.
4. This tree is a BST, and use first value of the pair as BST key.
5. Insert pair at the correct BST location. If conflicts, we’ve found 1 overlapping pair.

The code for searching a intersect, and insert a pair looks like this:

Node x = root;
while (x != null) {
    if (x.interval.intersects(lo, hi)) 
        return x.interval;
    else if (x.left == null)  x = x.right;
    else if (x.left.max < lo) x = x.right;
    else                      x = x.left;
}
return null;