9
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ Are these axis-aligned rectangles or not? (You can do it either way, but it is easier if they are.) $\endgroup$ – Louis Apr 20 '12 at 15:16
  • $\begingroup$ @Louis, let's simplify it a little bit, let's assume there are axis-aligned rectangles, but of course general case is more interesting $\endgroup$ – com Apr 20 '12 at 16:14
  • $\begingroup$ Which points of a rectangle are event points? All corners, the top left one...? $\endgroup$ – Raphael Apr 22 '12 at 11:19
  • $\begingroup$ @Raphael, only x's are event points $\endgroup$ – com Apr 22 '12 at 12:48
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much for your reply. There are few things I want to make clear about general case. $Q$ - event points are $x$ presorted coordinate, $T$ - status - "uncovered" intervals, as I understood it's interval correspondent to $x_{i}$ of one of the $R$'s which is uncovered by any other $R_{i}, i \ge 1$. The part with $R_{0}$ I didn't understand. I think on every iteration (adding) we should check if interval intersect the $R_{0}$, is it right? $\endgroup$ – com Apr 21 '12 at 19:16
  • $\begingroup$ For the general case, basically I am assuming that you know how to construct the whole planar map induced by the rectangles, and then I am arguing that a face of this is entirely in $R_i$ if one of its bounding edges is on the "inside" of $R_i$. You can track this in the usual sweep algorithms (e.g., from the "Marks" book) by just recording the "inside" and "outside" directions of the segments when they are added to the sweep line. $\endgroup$ – Louis Apr 21 '12 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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