cover and hide with squares

Question

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?

Answer 1

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. (SIAM journal link.)

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.