MathOverflow is a question and answer site for professional mathematicians. 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

I am studying two numbers, related to squares, that can characterize a polygon P:

  1. MinCoverNumber = the minimum number of axis-aligned squares required to exactly cover P (the covering squares may overlap, but may not cover points outside P). For example: a square has MinCoverNumber=1. A 4-by-5 rectangle has MinCoverNumber=2, as it can be covered by 2 overlapping 4-by-4 squares. An L-shape has MinCoverNumber=3, if it is fat enough. A triangle has MinCoverNumber=$\infty$, because it cannot be exactly covered by a finite number of axis-aligned squares.

  2. MaxHideNumber = the maximum number of dots that can be placed inside P, such that no two dots can be covered by a single square. For example, a square has MaxHideNumber=1, a 4-by-5 rectangle has MaxHideNumber=2, etc.

Obivously, MinCoverNumber is an upper bound for MaxHideNumber, for example: if MinCoverNumber=3 (such as a fat L-shape), then for every 4 dots, at least 2 of them are covered by one square, therefore MaxHideNumber$\leq$3. However, I don't know if this is also a lower bound.

If MinCoverNumber=2, then obviously MaxHideNumber=2, but if MinCoverNumber=3 (i.e. a polygon that cannot be covered by 2 squares), I haven't managed to prove that MaxHideNumber=3 (i.e. it is possible to hide 3 dots such that no 2 are coverable by a single square). I also haven't managed to find a counter-example.

So, my question is:

Is it possible to find an axis-aligned polygon P, such that MaxHideNumber(P) < MinCoverNumber(P)?

An alternative presentation of the question for MinCoverNumber=3:

Is it possible to find an axis-aligned polygon P, such that P cannot be covered by 2 squares, but in every set of 3 dots in P, there is a subset of 2 dots that are covered by a single square contained in P?

share|cite|improve this question
up vote 5 down vote accepted

Problem 1 is solved in a paper I coauthored:

Covering orthogonal polygons with squares L. J. Aupperle and H. E. Conn and J. M. Keil and Joseph O'Rourke Proc. 26th Allerton Conf. Commun. Control Comput., pp. 97-106, 1988. (link to PDF scan link).


That paper establishes a time complexity of $O(n^{5/2})$, but it was subsequently improved to $O(n^{3/2})$. Here the polygon $P$ is assumed to have vertices on the integer lattice, and $n$ is the number of unit squares ("pixels") inside $P$.

Problem 2 is called the maximum hidden vertex set problem, although usually visibility is just by straight lines-of-sight, rather than being enclosed in a square, which is a type of restricted visibility. I am not recalling work resolving your exact question, but my guess is (a) it exists and (b) you could find it by searching on that phrase, e.g.,

Antonio L. Bajuelos, Santiago Canales, Gregorio Hernández, A. Mafalda Martins.
"Estimating the Maximum Hidden Vertex Set in Polygons." 2008. (ACM link)

See also the related MO question, "Upper bounds on art gallery problems using independent witnesses," and that alternative terminology for the same concept.

(After clarifications):

I think (but am not certain) that your question is addressed and answered positively in this paper:

Michael O. Albertson and Claire J. O’Keefe. "Covering Regions with Squares." SIAM. J. on Algebraic and Discrete Methods, 2(3), 240–243.

Here's the abstract:

A unit square in $R^2 $ whose corners are integer lattice points is called a block. A board consists of a finite set of blocks. Given a board B, its graph $G(B)$ has vertices corresponding with the blocks of B, and two vertices of $G(B)$ are joined by an edge provided the corresponding blocks are contained in a square subset of B. If B is simply connected, then $G(B)$ is perfect.

share|cite|improve this answer
The links are interesting, but note that my question is not algorithmic (- how to find the minimum/maximum set), my question is theoretic (- are the two numbers always equal?) – Erel Segal-Halevi Jul 12 '13 at 7:18
I see; sorry to not understand. So your question is a variant of Michael Biro's, but with a different notion of "visibility"... – Joseph O'Rourke Jul 12 '13 at 10:44
Exactly. We happened to have a very similar question in the same month... and we didn't coordinate :) – Erel Segal-Halevi Jul 12 '13 at 12:12
If I understand it correctly, "$G(B)$ is perfect" answers the question negatively. MaxHideNumber(P) = independence number of $G(B)$, MinCoverNumber(P) = clique cover number of $G(B)$, therefore MaxHideNumber(P) = MinCoverNumber(P) for every lattice polygon $P$. – Jan Kyncl Jul 12 '13 at 20:22
@Joseph: I see... well, we could also perhaps just say that "it answers the question" :) – Jan Kyncl Jul 12 '13 at 23:57

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.