Rectangle Coverage by Sweep Line
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&#39;$ 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&#39;$ 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.