Hole Problems for Rectangles in the Plane
Gregory J. E. Rawlins, Peter Widmayer, Derick Wood · SIAM Journal on Discrete Mathematics · 1988
Given a set of n rectangles with sides parallel to the coordinate axes, we show how to determine whether their union, viewed as a set of disjoint polygons, has a hole. The algorithm presented needs no more than $O( n\log n )$ time and $O( n )$ space, which is shown to be optimal. However, in practice it is also necessary to know the locations of holes, if there are any. We present an algorithm to determine the locations of all h holes in $O( n\log n + h )$ time and $O( n )$ space, which is again optimal. The algorithm computes a point within each hole, representing the location of the hole. The efficiency of these and several other algorithms follows from some simple combinatorial arguments about sets of rectangles in the plane.