patternMinor
Efficient algorithm for finding maximum subset of intersecting rectangles
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
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 countSolution
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.
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.