Esta respuesta es más o menos una formalización de la intuición presentado por Nick Gill en su respuesta. El comienzo de las piezas son en su mayoría sólo formalidades, por lo que probablemente puede saltar hacia abajo en el diagrama.
Deje $C$ ser una alineado al eje ortogonal polígono. Siguiente Chaikan et al., consideraremos $C$ como una unión de plazas. Para cualquier cuadrado de $x \in C$, definimos $$R(x) = \{ y \in C \;|\; \exists \text{ a rectangle in $C$ containing $x$ and $s$}\}$$
con el entendimiento de que $x\in R(x)$. A continuación, vamos a definir un pre-order $\leq$ a $C$ por $$ x \leq y \iff R(x) \subseteq R(y)$$
Deje $x$ e $y$ forma un anti-rectángulo y deje $R(z) \subseteq R(x)$. Entonces, podemos ver que $z$ e $y$ también forma un anti-rectángulo. De ello se sigue que dado un anti-rectángulo $\{x_1, x_2, \ldots, x_k\}$, podemos encontrar otro anti-rectángulo $\{x_1', x_2', \ldots, x_k'\}$ de igual cardinalidad donde cada una de las $x_i'$ es el elegido para ser el mínimo elemento que $x_i' \leq x_i$. De hecho, se puede construir un máximo de anti-rectángulo mediante la selección de un representante de cada uno de los mínimos de clases de equivalencia (que se define en la forma habitual por la pre-orden).
Ahora queda por mostrar que si $C$ no contiene agujeros, entonces existe al menos un mínimo esquina de la plaza. Que en realidad se muestran ligeramente más: que hay al menos una esquina de la plaza de la $x$ en un "soporte de borde" (por Chaikan et terminología) tal que $R(x)$ es un rectángulo. Observar que si $R(x)$ es un rectángulo, entonces $x$ es mínima; la dejamos como ejercicio para el lector a construir un ejemplo que muestra que el recíproco es falso.
Cada arista $C$ pueden ser clasificados por las plazas en sus extremos. Un borde puede tener dos, uno, cero o esquinas en sus extremos. En la terminología establecidos en Nick Gill y la respuesta, corresponderían a $RR$, $RL$ (o $LR$), y $LL$ bordes respectivamente (también, $RR$ bordes corresponden a "apoyo bordes" en Chaikan et al de la terminología).
La clave lema que vamos a necesitar es que si $C$ es un simple, polígono ortogonal, entonces tiene más estrictamente $RR$ bordes de $LL$ bordes. En primer lugar, vamos a tomar como dado que hay más estrictamente $R$ esquinas de $L$ rincones (de nuevo, como se define en el Nick Gill y la respuesta) en $C$. Vamos $rr$, $ll$, y $rl$ el número de $RR$, $LL$, y $RL$ bordes. Ahora trataremos de contar el número de cada tipo de la esquina a través de conteo en cada borde. Cada una de las $RR$ edge vamos a contar como dos $R$ esquinas, cada una de las $LL$ borde como dos $L$ esquinas, y cada una de las $RL$ borde como una $R$ e una $L$ esquina. A contar de esta manera, terminamos de contar cada esquina exactamente dos veces. Por lo tanto, tenemos $2r = 2rr+rl$ e $2l = 2ll+rl$. Por lo tanto, $0 < 2r - 2l = 2rr - 2ll$ y por lo tanto, hay más estrictamente $RR$ bordes de $LL$ bordes.
Considere el siguiente diagrama de una $RR$ borde:
![enter image description here]()
Las líneas negras gruesas indican límites conocidos de $C$. Los cuadrados rojos, $x$ e $y$ son las esquinas de la $RR$ de ventaja. Los cuadrados azules $a$ e $b$ está en el borde de plazas directamente por encima de $x$ e $y$ respectivamente (es decir: todos los cuadrados entre el $x$ e $a$ y entre el $y$ e $b$ son plazas interiores).
Si no existiera el borde de las plazas de la región sombreada, a continuación, $R(x)$ sería un rectángulo, y nos gustaría hacer. Así, vamos a $c$ ser un borde cuadrado en la región sombreada. Además, elegimos $c$ a uno de los borde de las plazas más cercano a la $xy$ extremo (es decir: $c$ es uno de los más meridionales de borde de plazas en la región sombreada). Llame al borde correspondiente a $c$, $E$. Tenga en cuenta que si bien puede haber más de una vez que dicho borde, para nuestros propósitos, sólo tendrá que elegir uno.
Ahora podemos inferir que $E$ debe ser un $LL$ de ventaja. Por la construcción de la región sombreada, los extremos de $E$ debe estar dentro de la región sombreada (de lo contrario, se violaría uno de los caminos claros entre el $x$ e $a$ o $y$ e $b$). Por lo tanto, si uno de los extremos de $E$ fueron una esquina, contradice la elección de $c$ como uno de los más meridionales de bordes cuadrados. Finalmente, se observa que el $E$ puede ser identificada de ese modo al $RR$ borde correspondiente a $xy$. De otra manera, una vez más, contradice la elección de $c$ como el más cercano a $xy$.
Así, llegamos a la conclusión de que cualquier $RR$ borde donde las esquinas no son mínimos, pueden ser identificados con un $LL$ de ventaja. Puesto que hay más $RR$ bordes de $LL$ bordes, uno de ellos debe contener un mínimo de esquina.
