There are $n$ green axis-parallel squares on the plane. You may scale and translate each square arbitrarily, as long as no two of them intersect. Now you have to put paiwise-disjoint red squares on the plane, such that each green square intersects 4 red squares. What is the minimum number of red squares required (as a function of $n$)?
The most compact arrangement of green squares that I could come up with is in a grid, like this:
The number of red squares required (assuming $n$ is a square of an integer) is $(\sqrt{n}+1)^2 = n+O(\sqrt{n})$.
Is there an arrangement that requires a smaller number of red squares?
(NOTE: squares can be of different sizes).
For four green squares, your formula suggests nine red squares are needed.
You can certainly do it with eight: pair the green squares with a narrow corridor in each pair, and put four small red squares in each corridor.