Efficient algorithm for rectangle containment
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).