Finding missing range in multidimensional domain
This problem is known in computational geometry as Klee's measure problem. 

The solution to this problem in 2D case is based on an approach known as Sweep Line Algorithm and is know as Bentley's algorithm.

Conceptually, it is as easy as sweeping the plane by a vertical line from left to right. An intersection of a vertical line with a set of rectangles is a set of one-dimensional ranges. That way, a two-dimensional problem is reduced to $O(N)$ one-dimensional problems. 

Here is an overview:


Represent each rectangle as a pair of vertical ranges. One range on the left-hand side of it and one range on the right-hand side of it. 
Sort vertical ranges by their $x$ coordinate. That should take $O(N \log N)$ time. 
Scan the resulting $2N$ vertical ranges in increasing order of $x$ coordinate while maintaining a set of active ranges. When encountering a left-hand side of the rectangle the corresponding range is added to the set, crossing a right-hand side removes the corresponding range. 
As you finish processing updates to the set at the given $x$ coordinate verify that the current set of active ranges covers your $y$ range completely. 


An efficient implementation of this algorithm maintains a set of ranges in a data structure that supports $O(\log N)$ update and query operations. It can be implemented by building a Segment Tree for all different $y$ coordinates and maintaining a total covered range in that segment tree. 

It gives an overall $O(N \log N)$ complexity for a 2D algorithm.

This algorithm can be generalized to higher dimensions with $O(N^{d - 1} \log N)$ complexity. However, there are better algorithms for $d &gt; 3$. You can find references in the Wikipedia article for Klee's measure problem.