Skip to main content
added 255 characters in body
Source Link

This is an attempt to complement Nick Gill's answer. If it is correct (I am not sure), it should be merged into his answer.

Proposition: In every hole-free polygon, there exists a corner square that lies in exactly one maximal subrectangle.

Proof: Observe that as one moves clockwise around the perimeter of the polygon, one must go either left or right at various stages. One obtains a sequence: $R,R,L, R, L \cdots$ and it is clear that the number of $R$'s is 4 more than the number of $L$'s. Therefore there must be a pair of two adjacent $R$'s.

Assume w.l.o.g. that there is such a pair such that the side between the corners faces west. Consider the maximal rectangle that covers the two $R$ corners (red in the pictures below). This rectangle must run into at least one eastern side. There are two cases:

Case A: The eastern side is connected to an $R$ corner adjacent to the $RR$ pair at the north or south:

Case A

In this case, the middle $R$ corner is contained in exactly one maximal rectangle (the red one) and we are done.

Case B: The eastern side is between two adjacent $L$ corners:

Case B

By the construction, it is clear that this $LL$ pair cannot be used in the same way with any other $RR$ pair.

Now we know that this cannot happen to all consecutive $R$-corners, because the number of $R$-corners exceeds the number of $L$-corners by $4$.

EDIT: I am not sure about the latter counting argument. What if there is a sequence LLL, such that the first LL pair matches an RR pair, and the second LL pair matches a disjoint RR pair?

RR RR LLL

This is an attempt to complement Nick Gill's answer. If it is correct (I am not sure), it should be merged into his answer.

Proposition: In every hole-free polygon, there exists a corner square that lies in exactly one maximal subrectangle.

Proof: Observe that as one moves clockwise around the perimeter of the polygon, one must go either left or right at various stages. One obtains a sequence: $R,R,L, R, L \cdots$ and it is clear that the number of $R$'s is 4 more than the number of $L$'s. Therefore there must be a pair of two adjacent $R$'s.

Assume w.l.o.g. that there is such a pair such that the side between the corners faces west. Consider the maximal rectangle that covers the two $R$ corners (red in the pictures below). This rectangle must run into at least one eastern side. There are two cases:

Case A: The eastern side is connected to an $R$ corner adjacent to the $RR$ pair at the north or south:

Case A

In this case, the middle $R$ corner is contained in exactly one maximal rectangle (the red one) and we are done.

Case B: The eastern side is between two adjacent $L$ corners:

Case B

By the construction, it is clear that this $LL$ pair cannot be used in the same way with any other $RR$ pair.

Now we know that this cannot happen to all consecutive $R$-corners, because the number of $R$-corners exceeds the number of $L$-corners by $4$.

This is an attempt to complement Nick Gill's answer. If it is correct (I am not sure), it should be merged into his answer.

Proposition: In every hole-free polygon, there exists a corner square that lies in exactly one maximal subrectangle.

Proof: Observe that as one moves clockwise around the perimeter of the polygon, one must go either left or right at various stages. One obtains a sequence: $R,R,L, R, L \cdots$ and it is clear that the number of $R$'s is 4 more than the number of $L$'s. Therefore there must be a pair of two adjacent $R$'s.

Assume w.l.o.g. that there is such a pair such that the side between the corners faces west. Consider the maximal rectangle that covers the two $R$ corners (red in the pictures below). This rectangle must run into at least one eastern side. There are two cases:

Case A: The eastern side is connected to an $R$ corner adjacent to the $RR$ pair at the north or south:

Case A

In this case, the middle $R$ corner is contained in exactly one maximal rectangle (the red one) and we are done.

Case B: The eastern side is between two adjacent $L$ corners:

Case B

By the construction, it is clear that this $LL$ pair cannot be used in the same way with any other $RR$ pair.

Now we know that this cannot happen to all consecutive $R$-corners, because the number of $R$-corners exceeds the number of $L$-corners by $4$.

EDIT: I am not sure about the latter counting argument. What if there is a sequence LLL, such that the first LL pair matches an RR pair, and the second LL pair matches a disjoint RR pair?

RR RR LLL

Source Link

This is an attempt to complement Nick Gill's answer. If it is correct (I am not sure), it should be merged into his answer.

Proposition: In every hole-free polygon, there exists a corner square that lies in exactly one maximal subrectangle.

Proof: Observe that as one moves clockwise around the perimeter of the polygon, one must go either left or right at various stages. One obtains a sequence: $R,R,L, R, L \cdots$ and it is clear that the number of $R$'s is 4 more than the number of $L$'s. Therefore there must be a pair of two adjacent $R$'s.

Assume w.l.o.g. that there is such a pair such that the side between the corners faces west. Consider the maximal rectangle that covers the two $R$ corners (red in the pictures below). This rectangle must run into at least one eastern side. There are two cases:

Case A: The eastern side is connected to an $R$ corner adjacent to the $RR$ pair at the north or south:

Case A

In this case, the middle $R$ corner is contained in exactly one maximal rectangle (the red one) and we are done.

Case B: The eastern side is between two adjacent $L$ corners:

Case B

By the construction, it is clear that this $LL$ pair cannot be used in the same way with any other $RR$ pair.

Now we know that this cannot happen to all consecutive $R$-corners, because the number of $R$-corners exceeds the number of $L$-corners by $4$.