An improved algorithm for the rectangle enclosure problem

Given a set of n rectangles in the plane, with sides parallel to the coordinate axes, the rectangle enclosure problem consists of finding all q pairs of rectangles such that one rectangle of the pair encloses the other. In this note we present an alternative algorithm to the one by Vaishnavi and Wood; while both techniques have worst-case running time O(nlog²n + q), ours uses optimal storage O(n) rather than O(nlog²n) of Vaishnavi and Wood. Our algorithm works entirely in-place and uses very conventional data structures.