# [Question] Axis Aligned Rectangles

### 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;
``````