Teorema de las dos orejas

Todo polígono simple con más de tres vértices tiene al menos dos orejas

Un polígono triangulado. Los dos vértices de los extremos de la cadena de triángulos forman orejas. Sin embargo, este polígono también tiene otras orejas que no son evidentes en esta triangulación.

En geometría , el teorema de las dos orejas establece que todo polígono simple con más de tres vértices tiene al menos dos orejas , vértices que pueden eliminarse del polígono sin introducir ningún cruce. El teorema de las dos orejas es equivalente a la existencia de triangulaciones de polígonos . Se atribuye con frecuencia a Gary H. Meisters, pero fue demostrado antes por Max Dehn .

Enunciado del teorema

Un polígono simple es una curva cerrada simple en el plano euclidiano que consta de un número finito de segmentos de línea en una secuencia cíclica, con cada dos segmentos de línea consecutivos que se encuentran en un punto final común, y sin otras intersecciones. Por el teorema de la curva de Jordan , separa el plano en dos regiones, una de las cuales (el interior del polígono) está acotada. Una oreja de un polígono se define como un triángulo formado por tres vértices consecutivos del polígono, de modo que su borde se encuentra completamente en el interior del polígono. El teorema de las dos orejas establece que todo polígono simple que no sea en sí mismo un triángulo tiene al menos dos orejas. ^[1] ${\displaystyle u,v,w}$ ${\displaystyle uw}$

Relación con las triangulaciones

Una oreja y sus dos vecinas forman un triángulo dentro del polígono que no es atravesado por ninguna otra parte del polígono. Quitar un triángulo de este tipo produce un polígono con menos lados, y quitar orejas repetidamente permite triangular cualquier polígono simple . Por el contrario, si se triangula un polígono, el dual débil de la triangulación (un grafo con un vértice por triángulo y una arista por par de triángulos adyacentes) será un árbol y cada hoja del árbol formará una oreja. Como todo árbol con más de un vértice tiene al menos dos hojas, todo polígono triangulado con más de un triángulo tiene al menos dos orejas. Por lo tanto, el teorema de las dos orejas es equivalente al hecho de que todo polígono simple tiene una triangulación. ^[2]

Los algoritmos de triangulación basados ​​en este principio se han denominado algoritmos de recorte de orejas . Aunque una implementación ingenua es lenta, el recorte de orejas se puede acelerar mediante la observación de que un triple de vértices consecutivos de un polígono forma una oreja si y solo si el vértice central del triple es convexo y el triple forma un triángulo que no contiene ningún vértice reflejo. Al mantener una cola de triples con esta propiedad, y eliminar repetidamente una oreja de la cola y actualizar los triples adyacentes, es posible realizar el recorte de orejas en el tiempo , donde es el número de vértices de entrada y es el número de vértices reflejos. ^[3] ${\displaystyle O{\bigl (}n(r+1){\bigr )}}$ ${\displaystyle n}$ ${\displaystyle r}$

Si se triangula un polígono simple, entonces un triple de vértices consecutivos forma una oreja si es un vértice convexo y ninguno de sus otros vecinos en la triangulación se encuentra en el triángulo . Al probar todos los vecinos de todos los vértices, es posible encontrar todas las orejas de un polígono simple triangulado en tiempo lineal . ^[4] Alternativamente, también es posible encontrar una sola oreja de un polígono simple en tiempo lineal, sin triangular el polígono. ^[5] ${\displaystyle u,v,w}$ ${\displaystyle v}$ ${\displaystyle uvw}$

Tipos de vértice relacionados

Un polígono con solo dos orejas (sombreado claro), ninguna de las cuales está expuesta

Se dice que una oreja está expuesta cuando su vértice central pertenece a la envoltura convexa del polígono. Sin embargo, es posible que un polígono no tenga orejas expuestas. ^[6]

Las orejas son un caso especial de un vértice principal , un vértice tal que el segmento de línea que conecta los vecinos del vértice no cruza el polígono ni toca ningún otro vértice del mismo. Un vértice principal para el cual este segmento de línea se encuentra fuera del polígono se llama boca . De manera análoga al teorema de las dos orejas, cada polígono simple no convexo tiene al menos una boca. Los polígonos con el número mínimo de vértices principales de ambos tipos, dos orejas y una boca, se denominan polígonos antropomorfos . ^[7] Encontrar y eliminar repetidamente una boca de un polígono no convexo eventualmente lo convertirá en la envoltura convexa del polígono inicial. Este principio se puede aplicar a los polígonos circundantes de un conjunto de puntos; estos son polígonos que usan algunos de los puntos como vértices y contienen el resto de ellos. Eliminar una boca de un polígono circundante produce otro polígono circundante, y la familia de todos los polígonos circundantes se puede encontrar invirtiendo este proceso de eliminación de boca, comenzando desde la envoltura convexa. ^[8]

Historia y pruebas

El teorema de las dos orejas se atribuye a menudo a un artículo de 1975 de Gary H. Meisters, de donde se originó la terminología "oreja". ^[1] Sin embargo, el teorema fue demostrado anteriormente por Max Dehn (circa 1899) como parte de una prueba del teorema de la curva de Jordan . Para demostrar el teorema, Dehn observa que cada polígono tiene al menos tres vértices convexos. Si uno de estos vértices, v , no es una oreja, entonces puede estar conectado por una diagonal a otro vértice x dentro del triángulo uvw formado por v y sus dos vecinos; x puede elegirse para que sea el vértice dentro de este triángulo que está más alejado de la línea uw . Esta diagonal descompone el polígono en dos polígonos más pequeños, y la descomposición repetida por orejas y diagonales finalmente produce una triangulación de todo el polígono, a partir de la cual se puede encontrar una oreja como una hoja del árbol dual. ^[9]

Referencias

1. Meisters, GH (1975), "Los polígonos tienen orejas", The American Mathematical Monthly , 82 (6): 648–651, doi :10.2307/2319703, JSTOR  2319703, MR  0367792.
2. O'Rourke, Joseph (1987), Teoremas y algoritmos de la galería de arte , Serie internacional de monografías sobre informática, Oxford University Press, ISBN 0-19-503965-3, Sr.  0921437.
3. Held, M. (2001), "FIST: triangulación rápida de polígonos a nivel industrial", Algorithmica , 30 (4): 563–596, doi :10.1007/s00453-001-0028-4, MR  1829495, S2CID  1317227
4. Highnam, PT (1982), "Las orejas de un polígono", Information Processing Letters , 15 (5): 196–198, doi :10.1016/0020-0190(82)90116-8, MR  0684250
5. ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried (septiembre de 1993), "Cortar una oreja con el método de podar y buscar", Pattern Recognition Letters , 14 (9): 719–722, Bibcode :1993PaReL..14..719E, doi :10.1016/0167-8655(93)90141-y
6. Meisters, GH (1980), "Vértices principales, puntos expuestos y orejas", The American Mathematical Monthly , 87 (4): 284–285, doi :10.2307/2321563, JSTOR  2321563, MR  0567710.
7. Toussaint, Godfried (1991), "Polígonos antropomórficos", The American Mathematical Monthly , 98 (1): 31–35, doi :10.2307/2324033, JSTOR  2324033, MR  1083611.
8. Yamanaka, Katsuhisa; Avis, David ; Horiyama, Takashi; Okamoto, Yoshio; Uehara, Ryuhei; Yamauchi, Tanami (2021), "Enumeración algorítmica de polígonos circundantes", Matemáticas aplicadas discretas , 303 : 305–313, doi : 10.1016/j.dam.2020.03.034 , MR  4310502
9. Guggenheimer, H. (1977), "El teorema de la curva de Jordan y un manuscrito inédito de Max Dehn" (PDF) , Archivo de Historia de las Ciencias Exactas , 17 (2): 193–200, doi :10.1007/BF02464980, JSTOR  41133486, MR  0532231, S2CID  121684753.

Enlaces externos

• El teorema de las dos orejas, Godfried Toussaint