Rectangle Coverage by Sweep Line

Question

I am given an exercise unfortunately I didn't succeed by myself.

There is a set of rectangles $R_{1}..R_{n}$ and a rectangle $R_{0}$. Using plane sweeping algorithm determine if $R_{0}$ is completely covered by the set of $R_{1}..R_{n}$.

For more details about the principle of sweep line algorithms see here.

Let's start from the beginning. Initially we know sweep line algorithm as the algorithm for finding line segment intersectionswhich requires two data structures:

• a set $Q$ of event points (it stores endpoints of segments and intersections points)
• a status $T$ (dynamic structure for the set of segments the sweep line intersecting)

The General Idea: assume that sweep line $l$ is a vertical line that starts approaching the set of rectangles from the left. Sort all $x$ coordinates of rectangles and store them in $Q$ in increasing order - should take $O(n\log n)$. Start from the first event point, for every point determine the set of rectangles that intersect at given $x$ coordinate, identify continuous segments of intersection rectangles and check if they cover $R_{0}$ completely at current $x$ coordinate. With $T$ as a binary tree it's gonna take $O(\log n)$. If any part of $R_{0}$ remains uncovered that $R_{0}$ is not completely covered.

Details: The idea of segment intersection algorithm was that only adjacent segments intersect. Based on this fact we built status $T$ and maintained it throughout the algorithm. I tried to find a similar idea in this case and so far with no success, the only thing I can say is two rectangles intersect if their corresponding $x$ and $y$ coordinates overlap.

The problem is how to build and maintain $T$, and what the complexity of building and maintain $T$ is. I assume that R trees can be very useful in this case, but as I found it's very difficult to determine the minimum bounding rectangle using R trees.

Do you have any idea about how to solve this problem, and particularly how to build $T$?

Answer 1

Let's start with $n$ axis-aligned rectangles, since there is a kind of easy direct argument. We'll sweep a vertical line. The events are the endpoints of horizontal edges of the rectangles. As we sweep we maintain a set of intervals on the sweep line that are "uncovered" by $R_i$, $i\ge 1$:

• Add the vertical interval covered by the rectangle $R_i$ to the sweep line when we first encounter $R_i$
• Remove the vertical interval covered by the rectangle $R_i$ from the sweep line when it moves past $R_i$

It's easy to do this with a binary tree so that updates take $O(\log n)$ time. (The problem is, essentially, 1-dimensional. You figure out if the endpoints are in an uncovered interval and extend/merge appropriately when adding and lengthen them when removing.)

Then you just check that, in the span of $R_0$, none of the uncovered intervals ever intersect the vertical span of $R_0$. The whole thing is $O(n\log n)$ time an $O(n)$ space.

For the general case, the obvious trick is not quite so fast. Use the standard sweep line algorithm to compute the whole planar subdivision induced by the rectangles.

Clearly some disk-like set $F'$ of the faces covers $R_0$. By itself, this doesn't tell us enough, since what we are interested in is whether any of these faces is inside $R_0$ and outside the other rectangles. To do this, we modify the construction a little bit, so that when we add an edge, we tag one side with the identity of the rectangle it's inside. This adds $O(1)$ overhead, so the construction is $O(n^2\log n)$ time; with no assumptions on the rectangles, the output can be $\Omega(n^2)$ in size, so we are using that much space in the worst case, so the time is, "existentially optimal" though not "output sensitive".

Finally, $R_0$ is covered so long as none of the faces in $F'$ have only edges not tagged as being in one of the $R_i$. The point is that if an edge of $f$ is in $R_i$, then the whole of $f$ is as well. Imagine sweeping a line over $f$ orthogonally along this edge: it can only leave $R_i$ either outside of $f$ or $f$ is bounded by more than one edge of $R_i$.

So the conclusion is that the special case is $O(n\log n)$ and the general one is $O(n^2\log n)$ at least, but I suspect it can be improved.