Let $C$ be an axis-parallel orthogonal polygon with a finite number of sides. Define an anti-rectangle in $C$ as a set of small squares in $C$, such that no two of them are covered by a single large rectangle in $C$. Define a maximum anti-rectangle as an anti-rectangle that contains a maximum number of squares. For example, the following L-shape has a maximum anti-rectangle with 2 squares:
The following C-shape has a maximum anti-rectangle with 3 squares:
And the following shape has a maximum anti-rectangle with 5 squares:
When I try to build an anti-rectangle, I usually start with putting squares in the corners of $C$, because intuitively, the corners have the least chance of being covered by a rectangle. This raises the following conjecture:
For every $C$, there is a maximum anti-rectangle, which contains a corner square.
(- a corner square is a square with at least two adjacent sides that are in the boundary of $C$).
I found in Chaikan et al (1981) a proof that the conjecture is true when $C$ is linearly-convex (- contains every vertical or horizontal line that connects two of its points; like the L-shape above).
Their proof is not valid when $C$ is not linearly-convex, but I also cannot find a counter-example. What do you say?
CONCLUSION: Many thanks to all repliers. The conjecture is false when the polygon may have holes (as shown by dmotorp). It is true when the polygon is hole-free (as proven by Nick Gill and mhum).
UPDATE: I cited this thread in the following working paper. I hope it will be accepted.
Best Answer
Let $C$ be an axis-aligned orthogonal polygon. Following Chaikan et al., we'll consider $C$ as a union of squares. For any square $x \in C$, we define $$R(x) = \{ y \in C \;|\; \exists \text{ a rectangle in $C$ containing $x$ and $y$}\}$$ with the understanding that $x\in R(x)$. Next, we define a pre-order $\leq$ on $C$ by $$ x \leq y \iff R(x) \subseteq R(y)$$
Let $x$ and $y$ form an anti-rectangle and let $R(z) \subseteq R(x)$. Then, we can show that $z$ and $y$ also form an anti-rectangle. It follows that given an anti-rectangle $\{x_1, x_2, \ldots, x_k\}$, we can find another anti-rectangle $\{x_1', x_2', \ldots, x_k'\}$ of equal cardinality where each $x_i'$ is chosen to be a minimal element such that $x_i' \leq x_i$. In fact, we can construct a maximum anti-rectangle by selecting one representative from each of the minimal equivalence classes (defined in the usual way by the pre-order).
It now remains to show that if $C$ does not contain any holes, then there exists at least one minimal corner square. We will actually show slightly more: that there is at least one corner square $x$ on a "support edge" (by Chaikan et al's terminology) such that $R(x)$ is a rectangle. Observe that if $R(x)$ is a rectangle, then $x$ is minimal; we leave as an exercise for the reader to construct an example that shows that the converse is false.
Each edge in $C$ can be categorized by the squares at its endpoints. An edge can have either two, one, or zero corners at its endpoints. In the terminology laid out in Nick Gill's answer, these would correspond to $RR$, $RL$ (or $LR$), and $LL$ edges respectively (also, $RR$ edges correspond to "support edges" in Chaikan et al's terminology).
The key lemma we will need is that if $C$ is a simple, orthogonal polygon then it has strictly more $RR$ edges than $LL$ edges. First, we'll take as given that there are strictly more $R$ corners than $L$ corners (again, as defined in Nick Gill's answer) in $C$. Let $rr$, $ll$, and $rl$ be the number of $RR$, $LL$, and $RL$ edges. We will now try to count the number of each type of corner via counting each edge. Each $RR$ edge we'll count as two $R$ corners, each $LL$ edge as two $L$ corners, and each $RL$ edge as one $R$ and one $L$ corner. Counting in this way, we end up counting each corner exactly twice. So, we have $2r = 2rr+rl$ and $2l = 2ll+rl$. Thus, $0 < 2r - 2l = 2rr - 2ll$ and hence there are strictly more $RR$ edges than $LL$ edges.
Consider the following diagram of an $RR$ edge:
The heavy black lines indicate known boundaries of $C$. The red squares, $x$ and $y$ are the corners of the $RR$ edge. The blue squares $a$ and $b$ are the edge squares directly above $x$ and $y$ respectively (i.e.: all the squares between $x$ and $a$ and between $y$ and $b$ are interior squares).
If there were no edge squares in the shaded region, then $R(x)$ would be a rectangle and we would be done. So, let $c$ be an edge square in the shaded region. Furthermore, we choose $c$ to one of the edge squares closest to the $xy$ edge (i.e.: $c$ is one of the southernmost edge squares in the shaded region). Call the edge corresponding to $c$, $E$. Note that while there may be more than once such edge, for our purposes we will only need to choose one.
We now infer that $E$ must be an $LL$ edge. By construction of the shaded region, the endpoints of $E$ must lie inside the shaded region (otherwise, it would violate one of the clear paths between $x$ and $a$ or $y$ and $b$). Thus, if one of the endpoints of $E$ were a corner, it would contradict the choice of $c$ as one of the southernmost edge squares. Finally, we see that $E$ can be uniquely identified in this way with the $RR$ edge corresponding to $xy$. Otherwise, it would once again contradict the choice of $c$ as closest to $xy$.
So, we conclude that any $RR$ edge where the corners are not minimal can be uniquely identified with an $LL$ edge. Since there are more $RR$ edges than $LL$ edges, one of them must contain a minimal corner.