Given n rectangles coordinates, find area of region where k rectangles intersect?

Question

Given a list rectangles [R1, R2, R3] defined by their lower left and upper right [(x1, y1), (x2, y2)] coordinates, and a value k.

Is there an optimal way to find area where k rectangles overlap?

For example:

R1: [(1, 1), (5, 5)]
R2: [(4, 4), (7, 6)]
R3: [(3, 3), (8, 7)]

rectangles = [R1, R2, R3]
k = 2

The area which is overlapped by two rectangles is 8.

Brute force way to solve this is calculate the min and max of x-axis and y-axis coordinates and then used that create a grid and increment one for each cell within rectangle. At the end iterate over the grid to compute number of cells which have a value as k to find the solution.

The approach has a complexity of O(n^3), assuming each each rectangle is of size n x n and there are n rectangles.

Is there a run time optimal way to approach this problem?

Answer 1

The usual way to analyze collections of rectangles is with a sweep line algorithm. Imagine a vertical line that starts at the left of the collection and scans to the right. Store a set of the rectangles that currently intersect the line, initially empty. This set needs to be updated when the line passes a vertical side of any rectangle: adding or removing a rectangle in each case. To make scanning efficient, use a sorted list of the x coordinates of the verticals.

In this case, you'll also need a way to efficiently determine the intervals of the scan line that are covered by k or more rectangles. That can be done efficiently by maintaining an interval tree.

Depending on details, efficiency ought to be roughly O(n log n) for n rectangles with maybe an additional term for the maximum overlap depth. I'll let you work out the details.