HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Efficient algorithm for finding maximum subset of intersecting rectangles

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
maximumrectanglesefficientintersectingalgorithmforfindingsubset

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#18611, answer score: 2

Revisions (0)

No revisions yet.