A polynomial time complexity algorithm for the BoxDepth problem

Question

BoxDepth Problem:

Given $n$ rectangles, such that their sides are parralel to the coordinate axes ($x$ and $y$), Find a subset with maximum size such that the intersection of its members are not empty.

---

Question:

Provide a polynomial time algorithm for BoxDepth problem.

Note 1: The algorithm doesn't have to be optimal. The only thing that matters is the time complexity.

---

Note 2: I was thinking of taking each $2$ rectangles and check if their intersection is empty. But, that takes more than polynomial time. Is there a better algorithm that i'm not aware of?

Answer 1

Hint:

• Suppose that you know what the final intersection is, can you find all the rectangles that belong to your set?
• Intersection of two rectangles is a rectangle, so your final intersection is a rectangle too.
• The coordinate for the left side of the intersection rectangle is a coordinate for the left side of some rectangle in your set (and also for right, top, bottom, only each might be a different rectangle from your set).
• If you want the intersection to be non-empty, just pick a left-top side of your intersection and ensure that all your rectangles contain it.
• If you have $n$ rectangles, you have $n$ possibilities for the left side and $n$ for top, so with plain enumeration of all rectangles that would give you complexity $O(n^3)$.

I hope this helps $\ddot\smile$