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

• Louis: Try to do this for intervals and then if you can generalize it.
• Nejc: I am not entirely sure on how to approach the specifics, but the problem is solvable with plane sweep algorithm.
• user2175783: Seems promising. Perhaps somebody can elaborate
• greybeard: This(checking intersections in every pair of rectangles) looks $O(n^2)$ - what makes you claim $O(n^3)$?

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.

• user2175783: why divide A into 4 areas. Why not just 2?
• Karolis Juodelė: @user2175783, if you always divide along the same axis, the |intersect(A)| might never get to 0ドル$. If you alternate the axis of division, the algorithm is a tiny bit more verbose. Though that verbosity might be covered by "sensible subdivisions" I mentioned. No reason, then.
• Steven Stadnicki: This is generally known as a 'quadtree' style partition, and while you're right that the worst-case isn't $n\log n,ドル IIRC the 'average' case isn't either - it turns out to be more like $n^{3/2}$ because of the average height of a binary tree with $n$ nodes being more like $n^{1/2}$ than $\log n$.