Return to Answer

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 fact of simple, orthogonal polygons we need is that there are strictly more $RR$ edges than $LL$ edges.

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.

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 the $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$.

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$.

This answer is more or less just a formalization of the intuition put forward by Nick Gill in his answer. The beginning parts are mostly just formalities, so you can probably skip down to the diagram to see the interesting bits. The key was to match up edges, not corners.

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$ 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 fact of simple, orthogonal polygons we need is that there are strictly more $RR$ edges than $LL$ edges.

This answer is more or less just a formalization of the intuition put forward by Nick Gill in his answer. The beginning parts are mostly just formalities, so you can probably skip down to the diagram.

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 fact of simple, orthogonal polygons we need is that there are strictly more $RR$ edges than $LL$ edges.