Efficient algorithm for rectangle containment

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.

• One approach to derive a solution for an n+1-dimensional problem is "sweep" an n-dimensional "plane" through the relevant space; another is to subdivide the latter by such a plane, solve the problem recursively for those objects that don't intersect the dividing plane and another for those that do, and put together the results. – greybeard Nov 18 '15 at 11:20
• @vzn and D.W.: edited the question. It also seems to me that the first (greybeard's) comment leads to an efficient algorithm (a vertical "sweeping line" whose intersections with the rectangles undergo structural changes at "bifurcation points", which are projections of the vertical sides of the rectangles). – John Donn Nov 19 '15 at 7:17
• @vzn is this the "natural generalization" you had in mind? If not, perhaps you could post an answer. – John Donn Nov 19 '15 at 7:53
• " It also seems to me that the first (greybeard's) comment leads to an efficient algorithm.. " - though I tried, I could not find myself a suitable data structure to maintain the intersections of the vertical sweeping line with the rectangles (such that the overall operations required are little_o(n**2)). – John Donn Dec 3 '15 at 8:26

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).

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.

• I have a feeling you're describing a $O(k*n^2)$ algorithm here. Which is worse than what the OP is asking for. An important point is, what is the output of your checking on each dimension. Is it just marking the entries that is covered by something OR is it a record of which entries covers which? Because if it is the former, I don't think that information is enough to combine results of each dimensions. You kind of need to know the identity of the covering entry. In the latter version that you record the identity of the covering entry, the time taken is $O(n^2)$ for each D as I can think. – Apiwat Chantawibul Nov 19 '15 at 18:23
• agreed the complexity analysis is not trivial & not detailed/ filled out but think it is "close". the 1d range inclusions can be represented as a tree for the relation "A inside B". might write up the code sometime in ruby with some further inclination. can clarify details in Computer Science Chat for anyone with the time – vzn Nov 19 '15 at 23:42