Finding missing range in multidimensional domain

Let's suppose that I have a monodimensional numeric domain and a list of ranges in this domain defined as

class Range {
    int lowerBound;
    int upperBound;
}

then it's trivial to check if the union of the List is covering the entire domain. However in case of a bidimensional domain I have a List> and I'm no longer able to figure out if my rectangles (bidimensional ranges) are covering the entire area.

For example suppose that I have these ranges:

pair{ range{0, 7}, range{0, 5} },
pair{ range{7, 10}, range{0, 7} },
pair{ range{0, 5}, range{5, 10} },
pair{ range{5, 10}, range{7, 10} }

covering the domain as shown below.

How can I know that part of the domain isn't covered? (gray area in the picture). In other words is there an algorithm or a data-structure allowing to find if there exists at least one point in that domain that is not included in any of the rectangles? Is this solution also extensible to the n-dimensional case?

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 > 3$. You can find references in the Wikipedia article for Klee's measure problem.

StackExchange Computer Science Q#73814, answer score: 2