Efficient algorithm for rectangle containment

Question

Given a set of $n$ intervals on a line, there is a $O(n \log n)$ algorithm to find intervals which are contained in other intervals (e.g., Manber, "Using induction to design algorithms", 1988). Is there a $O(n \log n)$ algorithm for axis-aligned rectangles in higher dimensions?

I did some search on the internet, and tried to think about it myself, but could not find a generalization for higher dimensions. For example, given $n$ axis-aligned rectangles on the plane, the task is to find which rectangles are contained in other rectangles.

Answer 1

Have you considered multi-dimensional indexes? They are usually quite efficient to find overlapping or included rectangles.

I personally wrote a kind of prefix-sharing binary quadtree: Java sources It has an API for rectangles with a special method for searching rectangles included in another rectangle: PhTreeSolidF.queryInclude().

I'm not sure what the complexity is but it's roughly something in the order of O(n*k*log n) to build the tree and O(k*log n) for each query (k is the number of dimensions). For strongly clustered datasets it may even become something lose to O(1) for each query (I tested this with n=10.000.000 and 2<=k<=15).

Answer 2

there is a natural extension/ generalization of range searching for axis-aligned rectangles and higher dimensional hypercubes.

the problem reduces to checking range inclusion on each axis separately and then finding the intersection of the rectangles or hypercubes that "own" each 1-d range inclusion. it takes k*O(f(n)) where f(n) is the time to check a single dimension and k is the number of dimensions. this is based on the simple idea that for axis aligned rectangles/ hypercubes, a hypercube is in another hypercube iff all its separate sides are also. this does not determine merely overlapping axes-aligned rectangles/ hypercubes although a similar algorithm can do so.

am not aware of this published in the literature but its not complex and presumably it is cited somewhere at least in passing. the literature on this subject generally works with Kd-trees or quadtrees (2d case) and falls in the general category of database range query/ searching. the approach there would generally be to allow general geometric objects to be defined such as polygons and then find all the nodes in the Kd that the polygon overlaps with and do the range computation over all the nodes of the polygon(s) to determine intersections.