@EcirHana this will work, building up an spatial index can be extremly fast, i recommend using an PMR bucket Rectangle quadtree as spatial index.
Edited to add: of course, you don't rely on the R-tree to tell you if one polygon is inside another (it's based on minimum bounding rectangles so it can only give you an approximation). You use the R-tree to cheaply identify candidate inclusions which you then verify in the expensive way (checking that a point in one polygon is inside the other).
It costs O(n log n) to build the R-tree, so I don't think that's a concern.
Put your polygons into some kind of spatial lookup structure, for example an R-tree based on the minimum bounding rectangles for the polygons. Then you should be able to compute the containment relation that you're after in O(n log n). (Unless you're in a pathological case where many of the minimum bounding rectangles for your polygons overlap, which seems unlikely based on your description.)
Thanks for the answer but I don't think it will work. The problem is the time needed to build the lookup structure as it wont be reused again (i.e. the polygons may be different every time). Also, bboxes may or may not overlap, that's 50% and that's a lot :).
This is a very simplistic approach that doesn't need pathological cases at all to fail. Suppose there is a large polygon shaped like a "C", if we put a square in the free empty area of "C", why would you say that this square is contained by the other polygon ? Or maybe this is the pathological case and I'm adding unneeded requirements to a question that isn't mine.