Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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, unique? (i.e. can there be two different maximal square coverings of the same shape?)

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.