Efficient algorithm for finding maximum subset of intersecting rectangles

Question

What is an $O(n \log n)$ algorithm to find how big the largest subset of $n$ axis-aligned rectangles (in the plane) that contain a common point is? Perhaps by reducing this to a problem with such runtime?

An $O(n^{3})$ algorithm could be

for each of the n rectangles      
    for each of the 4 sides of the rectangle
        find the points where it intersects other rectangles and keep the set of those points 
        loop through the intersection points set and update the count

Answer 1

You need a sweep line and an interval tree (modified so that it reports a number instead of intervals). I assume this is a course book problem and you are familiar with its background.

Move the sweep line bottom to top, stop at each horizontal segment. If the segment is the bottom side of a rectangle, insert it as an interval into the interval tree and remove it when the sweep line hits the top side of that rectangle. At each step you can query the number of rectangles containing a point on the sweep line. There are $O(n)$ stops for sweep line, each one adds $O(\log n)$ for interval operations, so it is $O(n\log n)$ in total. The only remaining issue is to keep track of the maximum covered point in $O(1)$ at each step. You should be able to complete this solution.

Answer 2

I'm not 100%, this is correct, but some answer it better than no answer, so here I go.

Let's define an area to be a rectangle (not necessarily from the given set) and for area A define around(A) to be the set of rectangles (from given set) that fully contain A, define intersect(A) to be the set of rectangles (from given set) that are contained inside or intersect A. The solution of your program, restricted to A is definitely between |contain(A)| and |contain(A)| + |intersect(A)|.

The given rectangles all lie in a finite space. Let that be A. Subdivide A into 4 areas B1, B2, B3, B4 and distribute intersect(A) among them. Then f(A) = max(f(B1), f(B2), f(B3), f(B4)). This is a recursive relation, similar to quicksort, which should turn up to be $n \log n$ in average. Like quicksort it should have a sad ($n^2$ if you select sensible subdivisions) worst case performance as well.