How do I partition squares to avoid overlaps in polynomial time?

Question

Say that $A$ is a set of $n$ squares on the $xy$-plane. Let $k\leq n$ be the maximum integer such that $k$ of these squares overlap simultaneously (i.e they have a non-empty $k$-intersection as subsets of $\mathbb{R}^2$). Our goal is to find an algorithm that runs in polynomial time and partitions $A$ into no more than $4k$ sets, each of which contains only non-overlapping squares.

My approach

1. First do a "sweep" algorithm in all 4 different directions (i.e. keep adding non-overlapping squares ordered by their north, south, east, and west side respectively).
2. The above will create 4 non-overlapping set of squares. One for each direction
3. Remove these squares from the list (after every sweep)
4. Claim that this will reduce the maximum $k$ by $1$, which is enough to finish the proof, because we can now proceed by induction.

At the moment, I am having a hard time proving the last claim. Any ideas towards the right direction?

Answer 1

The claim is false. Consider, for example, the following arrangement of squares (with $k=2$):

No matter which direction you start the sweep from, neither of the large squares will get picked, because the small squares will always be first, so $k$ will not decrease.

Are the squares guaranteed to be axis-aligned? If so, the following algorithm works:

1. Sort the squares largest to smallest, and initialize $S_1, \dots, S_{4k}$ to be empty.
2. At each step, choose the largest square $ABCD$ not assigned to any $S_i$, and put it in the first $S_i$ that doesn't contain any squares overlapping with $ABCD$.
3. Repeat until all the squares are put into some $S_i$.

No square $ABCD$ can overlap more than $4(k-1)$ squares larger than $ABCD$: each larger square must contain one of $A$, $B$, $C$, or $D$, and each of $A$, $B$, $C$, and $D$ can only be contained in $k-1$ other squares. Therefore, at every iteration of step 2, at most $4(k-1)$ sets $S_i$ are ruled out. So if we have $4k$ sets (actually, $4k-3$ are enough) then we will always be able to put a square in one of them, and obtain a partition at the end.

But if the squares don't have to be axis-aligned, then it's possible for a larger square to overlap square $ABCD$, yet not contain any of the vertices $A$, $B$, $C$, and $D$, in which case this algorithm might not work.