# Maximal square covering

Let X be a shape in 2-dimensional space.

Define a square covering of X as a set of axis-aligned squares, whose union exactly equals X.

Note that some shapes don't have a finite square covering, for example, a circle or a triangle.

Define a maximal square covering of X as a square covering where each square is needed, i.e.:

• For every square, there is a point in X that is covered by that square only.
• No two squares can be replaced by a larger square that is contained in X.

Is a maximal square covering, defined in this way, is unique? (i.e. can there be two different maximal square coverings of the same shape?)

-
Are the squares necessarily parallel to the axes? –  Hagen von Eitzen May 19 '13 at 10:48
yes, the squares are axis-aligned, I edited the question –  Erel Segal-Halevi May 19 '13 at 20:27
Doesn't even matter - my counterexample below is axis-aligned –  Hagen von Eitzen May 19 '13 at 20:34

Let $Q(a,b,c,d)$ denote the square having $(a,b)$ and $(c,d)$ as opposite vertices. Then \begin{align}X&=Q(-10,1,10,21)\cup Q(-10,-21,10,-1)\cup Q(-2,-1,2,3)\\& = Q(-10,1,10,21)\cup Q(-10,-21,10,-1)\cup Q(-2,-3,2,1)\end{align} shows that uniqueness does not hold.

-
I see, you have a shape like a sandclock, with large squares at the top and bottom, and a short "neck" connecting them. The covering can include a square where the "neck" is either at the top or at the bottom, while the rest of the square overlaps one of the large squares. Thanks! –  Erel Segal-Halevi May 20 '13 at 4:21