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.
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&lt;=k&lt;=15).