3
$\begingroup$

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
$\endgroup$
4
  • 2
    $\begingroup$ Try to do this for intervals and then if you can generalize it. $\endgroup$
    – Louis
    Dec 4, 2013 at 19:56
  • $\begingroup$ I am not entirely sure on how to approach the specifics, but the problem is solvable with plane sweep algorithm. $\endgroup$
    – Nejc
    Dec 5, 2013 at 11:22
  • $\begingroup$ Seems promising. Perhaps somebody can elaborate $\endgroup$ Dec 5, 2013 at 15:18
  • $\begingroup$ This(checking intersections in every pair of rectangles) looks $O(n^2)$ - what makes you claim $O(n^3)$? $\endgroup$
    – greybeard
    Nov 23, 2016 at 8:10

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ why divide A into 4 areas. Why not just 2? $\endgroup$ Dec 4, 2013 at 18:37
  • $\begingroup$ @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. $\endgroup$ Dec 4, 2013 at 19:12
  • 1
    $\begingroup$ 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$. $\endgroup$ Dec 6, 2013 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.