polígono simple

Forma delimitada por segmentos de línea que no se cruzan

Dos polígonos simples (verde y azul) y un polígono que se interseca (rojo, en la parte inferior derecha, no simple)

En geometría , un polígono simple es un polígono que no se corta a sí mismo y no tiene agujeros. Es decir, es una curva de Jordan lineal por tramos que consta de un número finito de segmentos de recta . Estos polígonos incluyen como casos especiales los polígonos convexos , los polígonos estrellados y los polígonos monótonos .

La suma de los ángulos externos de un polígono simple es . Todo polígono simple de lados puede ser triangulado por sus diagonales, y según el teorema de la galería de arte su interior es visible desde algunos de sus vértices. ${\displaystyle 2\pi }$ ${\displaystyle n}$ ${\displaystyle n-3}$ ${\displaystyle \lfloor n/3\rfloor }$

Los polígonos simples se consideran comúnmente como la entrada para problemas de geometría computacional , incluida la prueba de puntos en polígonos , el cálculo de áreas , el casco convexo de un polígono simple , la triangulación y los caminos más cortos euclidianos .

Otras construcciones en geometría relacionadas con polígonos simples incluyen el mapeo de Schwarz-Christoffel , utilizado para encontrar mapas conformes que involucran polígonos simples, poligonalización de conjuntos de puntos, fórmulas constructivas de geometría sólida para polígonos y gráficos de visibilidad de polígonos.

Definiciones

Partes de un polígono simple

Un polígono simple es una curva cerrada en el plano euclidiano que consta de segmentos de línea recta que se unen de un extremo a otro para formar una cadena poligonal . ^[1] Dos segmentos de línea se encuentran en cada punto final y no hay otros puntos de intersección entre los segmentos de línea. Ningún subconjunto adecuado de segmentos de línea tiene las mismas propiedades. ^[2] El calificador simple a veces se omite, y se supone que la palabra polígono significa un polígono simple. ^[3]

Los segmentos de recta que forman un polígono se llaman aristas o lados . Un punto final de un segmento se llama vértice (plural: vértices) ^[2] o esquina . Las aristas y los vértices son más formales, pero pueden ser ambiguos en contextos que también involucran las aristas y los vértices de un gráfico ; Para evitar esta ambigüedad se pueden utilizar los términos más coloquiales lados y esquinas . ^[4] El número de aristas siempre es igual al número de vértices. ^[2] Algunas fuentes permiten que dos segmentos de línea formen un ángulo recto (180°), ^[5] mientras que otras no lo permiten, y en su lugar requieren que los segmentos colineales de una cadena poligonal cerrada se fusionen en un solo lado más largo. ^[6] Dos vértices son vecinos si son los dos extremos de uno de los lados del polígono. ^[7]

Los polígonos simples a veces se denominan polígonos de Jordan porque son curvas de Jordan ; El teorema de la curva de Jordan se puede utilizar para demostrar que dicho polígono divide el plano en dos regiones. ^[8] De hecho, la prueba original de Camille Jordan de este teorema tomó el caso especial de polígonos simples (enunciados sin prueba) como punto de partida. ^[9] La región dentro del polígono (su interior ) forma un conjunto acotado ^[2] topológicamente equivalente a un disco abierto según el teorema de Jordan-Schönflies , ^[10] con un área finita pero distinta de cero . ^[11] El polígono en sí es topológicamente equivalente a un círculo , ^[12] y la región exterior (el exterior ) es un conjunto abierto ilimitado y conectado , con área infinita. ^[11] Aunque la definición formal de un polígono simple es típicamente como un sistema de segmentos de línea, también es posible (y común en el uso informal) definir un polígono simple como un conjunto cerrado en el plano, la unión de estos segmentos de línea con el interior del polígono. ^[2]

Una diagonal de un polígono simple es cualquier segmento de línea que tiene dos vértices del polígono como puntos finales y que, por lo demás, es completamente interior al polígono. ^[13]

Propiedades

El ángulo interno de un polígono simple, en uno de sus vértices, es el ángulo comprendido por el interior del polígono en ese vértice. Un vértice es convexo si su ángulo interno es menor que (un ángulo llano, 180°) y cóncavo si el ángulo interno es mayor que . Si el ángulo interno es , el ángulo externo en el mismo vértice se define como su suplemento , el ángulo de giro de un lado dirigido al siguiente. El ángulo externo es positivo en un vértice convexo o negativo en un vértice cóncavo. Para cada polígono simple, la suma de los ángulos externos es (una vuelta completa, 360°). Así, la suma de los ángulos internos de un polígono simple con lados es . ^[14] ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle \theta }$ ${\displaystyle \pi -\theta }$ ${\displaystyle 2\pi }$ ${\displaystyle n}$ ${\displaystyle (n-2)\pi }$

Un polígono triangulado de 11 vértices: 11 lados y 8 diagonales forman 9 triángulos.

Todo polígono simple se puede dividir en triángulos que no se superponen por un subconjunto de sus diagonales. Cuando el polígono tiene lados, se producen triángulos, separados por diagonales. La partición resultante se llama triangulación de polígonos . ^[8] La forma de un polígono simple triangulado puede determinarse únicamente por los ángulos internos del polígono y por las razones cruzadas de los cuadriláteros formados por pares de triángulos que comparten una diagonal. ^[15] ${\displaystyle n}$ ${\displaystyle n-2}$ ${\displaystyle n-3}$

Según el teorema de las dos orejas , todo polígono simple que no sea un triángulo tiene al menos dos orejas , vértices cuyos dos vecinos son los extremos de una diagonal. ^[8] Un teorema relacionado establece que todo polígono simple que no es un polígono convexo tiene una boca , un vértice cuyos dos vecinos son los puntos finales de un segmento de línea que, por lo demás, es completamente exterior al polígono. Los polígonos que tienen exactamente dos orejas y una boca se llaman polígonos antropomorfos . ^[dieciséis]

Esta galería de arte poligonal de 42 vértices es completamente visible desde cámaras colocadas en los 4 vértices marcados.

Según el teorema de la galería de arte , en un polígono simple con vértices, siempre es posible encontrar un subconjunto de como máximo los vértices con la propiedad de que cada punto del polígono es visible desde uno de los vértices seleccionados. Esto significa que, para cada punto del polígono, existe un segmento de línea que conecta con un vértice seleccionado y pasa sólo por los puntos interiores del polígono. Una forma de demostrar esto es usar coloración de gráficos en una triangulación del polígono: siempre es posible colorear los vértices con tres colores, de modo que cada lado o diagonal de la triangulación tenga dos puntos finales de diferentes colores. Cada punto del polígono es visible para un vértice de cada color, por ejemplo uno de los tres vértices del triángulo que contiene ese punto en la triangulación elegida. Uno de los colores se utiliza en la mayoría de los vértices, lo que demuestra el teorema. ^[17] ${\displaystyle n}$ ${\displaystyle \lfloor n/3\rfloor }$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \lfloor n/3\rfloor }$

Casos especiales

Todo polígono convexo es un polígono simple. Otra clase importante de polígonos simples son los polígonos en forma de estrella , los polígonos que tienen un punto (interior o en su límite) desde el cual cada punto es visible. ^[2]

Un polígono monótono , con respecto a una línea recta , es un polígono en el que cada línea perpendicular a intersecta el interior del polígono en un conjunto conexo. De manera equivalente, es un polígono cuyo límite se puede dividir en dos cadenas poligonales monótonas, subsecuencias de aristas cuyos vértices, cuando se proyectan perpendicularmente sobre , tienen el mismo orden que en la cadena. ^[18] ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$

Problemas computacionales

Para comprobar si un punto está dentro del polígono, construya cualquier rayo que surja del punto y cuente sus intersecciones con el polígono. Si cruza sólo puntos interiores de aristas, un número impar de veces, el punto se encuentra dentro del polígono; si es así, el punto está afuera. Los rayos que atraviesan los vértices de un polígono o que contienen sus aristas necesitan un cuidado especial. ^[19]

Un polígono simple (interior sombreado en azul) y su casco convexo (que rodea las regiones azul y amarilla)

En geometría computacional , varias tareas computacionales importantes involucran entradas en forma de un polígono simple.

• La prueba de puntos en polígonos implica determinar, para un polígono simple y un punto de consulta , si se encuentra dentro de . Se puede resolver en tiempo lineal ; alternativamente, es posible procesar un polígono determinado en una estructura de datos, en tiempo lineal, de modo que las pruebas de puntos posteriores en el polígono se puedan realizar en tiempo logarítmico. ^[20] ${\displaystyle P}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle P}$
• Se conocen fórmulas simples para calcular el área del interior de un polígono. Estos incluyen la fórmula del cordón para polígonos arbitrarios, ^[21] y el teorema de Pick para polígonos con coordenadas de vértice enteras. ^{[12] [22]}
• La cáscara convexa de un polígono simple también se puede encontrar en tiempo lineal, más rápido que los algoritmos para encontrar cáscaras convexas de puntos que no han sido conectados en un polígono. ^[6]
• La construcción de una triangulación de un polígono simple también se puede realizar en tiempo lineal, aunque el algoritmo es complicado. También se puede utilizar una modificación del mismo algoritmo para probar si una cadena poligonal cerrada forma un polígono simple (es decir, si evita las autointersecciones) en tiempo lineal. ^[23] Esto también conduce a un algoritmo de tiempo lineal para resolver el problema de la galería de arte utilizando la mayoría de los puntos, aunque no necesariamente utilizando el número óptimo de puntos para un polígono determinado. ^[24] Aunque es posible transformar dos triangulaciones cualesquiera del mismo polígono entre sí mediante volteos que reemplazan una diagonal a la vez, determinar si se puede hacerlo usando solo un número limitado de volteos es NP-completo . ^[25] ${\displaystyle \lfloor n/3\rfloor }$
• Un camino geodésico , ^[26] el camino más corto en el plano que conecta dos puntos interiores a un polígono, sin cruzar al exterior, puede encontrarse en tiempo lineal mediante un algoritmo que utiliza la triangulación como subrutina. ^[27] Lo mismo ocurre con el centro geodésico , un punto en el polígono que minimiza la longitud máxima de sus caminos geodésicos hacia todos los demás puntos. ^[26]
• El polígono de visibilidad de un punto interior de un polígono simple, los puntos que son directamente visibles desde el punto dado mediante segmentos de línea interiores al polígono, se pueden construir en tiempo lineal. ^[28] Lo mismo ocurre con el subconjunto que es visible desde al menos un punto de un segmento de línea determinado. ^[27]

Otros problemas computacionales estudiados para polígonos simples incluyen construcciones de la diagonal más larga o del segmento de línea más largo interior a un polígono, ^[13] del cráneo convexo (el polígono convexo más grande dentro del polígono simple dado), ^{[29] [30]} y de varios esqueletos unidimensionales que se aproximan a su forma, incluido el eje medial ^[31] y el esqueleto recto . ^[32] Los investigadores también han estudiado la producción de otros polígonos a partir de polígonos simples utilizando sus curvas de desplazamiento , ^[33] uniones e intersecciones, ^[11] y sumas de Minkowski , ^[34] pero estas operaciones no siempre producen un polígono simple como resultado. Se pueden definir de una manera que siempre produzca una región bidimensional, pero esto requiere definiciones cuidadosas de las operaciones de intersección y diferencia para evitar crear características unidimensionales o puntos aislados. ^[11]

Construcciones relacionadas

Según el teorema de mapeo de Riemann , cualquier subconjunto abierto del plano simplemente conectado se puede mapear conformemente en un disco. El mapeo de Schwarz-Christoffel proporciona un método para construir explícitamente un mapa desde un disco a cualquier polígono simple utilizando ángulos de vértice específicos e imágenes previas de los vértices del polígono en el límite del disco. Estos prevértices normalmente se calculan numéricamente. ^[35]

El polígono negro es el bucle más corto que conecta cada punto rojo, una solución al problema del vendedor ambulante.

Cada conjunto finito de puntos en el plano que no se encuentra en una sola línea se puede conectar para formar los vértices de un polígono simple (permitiendo ángulos de 180°); por ejemplo, uno de esos polígonos es la solución al problema del vendedor ambulante . ^[36] Conectar puntos para formar un polígono de esta manera se llama poligonalización . ^[37]

Cada polígono simple puede representarse mediante una fórmula en geometría sólida constructiva que construye el polígono (como un conjunto cerrado que incluye el interior) a partir de uniones e intersecciones de semiplanos , donde cada lado del polígono aparece una vez como un semiplano en el fórmula. La conversión de un polígono de lados a esta representación se puede realizar en el tiempo . ^[38] ${\displaystyle n}$ ${\displaystyle O(n\log n)}$

El gráfico de visibilidad de un polígono simple conecta sus vértices mediante aristas que representan los lados y diagonales del polígono. ^[3] Siempre contiene un ciclo hamiltoniano , formado por los lados del polígono. La complejidad computacional de reconstruir un polígono que tiene un gráfico dado como gráfico de visibilidad, con un ciclo hamiltoniano específico como ciclo de lados, sigue siendo un problema abierto. ^[39]

Ver también

• Problema de la regla de Carpenter , sobre el movimiento continuo de un polígono simple hacia un polígono convexo
• Teorema de Erdős-Nagy , un proceso de reflexión de bolsas de un polígono simple no convexo para hacerlo convexo
• Red (poliedro) , un polígono simple que se puede doblar y pegar para formar un poliedro determinado.
• Polígono esférico , un concepto análogo en la superficie de una esfera
• Polígono débilmente simple , una generalización de polígonos simples que permite que los bordes se toquen de manera limitada

Referencias

1. Milnor, John W. (1950). "Sobre la curvatura total de los nudos". Anales de Matemáticas . 2da Serie. 52 : 248–257. doi :10.2307/1969467.
2. Preparata, Franco P .; Shamos, Michael Ian (1985). Geometría computacional: una introducción. Textos y Monografías en Informática. Springer-Verlag. pag. 18.doi : 10.1007 /978-1-4612-1098-6. ISBN 978-1-4612-1098-6.
3. Everett, Hazel; Corneil, Derek (1995). "Resultados negativos en la caracterización de gráficos de visibilidad". Geometría computacional: teoría y aplicaciones . 5 (2): 51–63. doi :10.1016/0925-7721(95)00021-Z. SEÑOR  1353288.
4. Arónov, Boris ; Seidel, Raimund ; Souvaine, Diane (1993). "Sobre triangulaciones compatibles de polígonos simples". Geometría computacional: teoría y aplicaciones . 3 (1): 27–35. doi : 10.1016/0925-7721(93)90028-5 . SEÑOR  1222755.
5. Malkevitch, José (2016). "¿Son una buena idea las definiciones precisas?". Columna de funciones de AMS . Sociedad Matemática Estadounidense.
6. McCallum, Duncan; Avis, David (1979). "Un algoritmo lineal para encontrar el casco convexo de un polígono simple". Cartas de procesamiento de información . 9 (5): 201–206. doi :10.1016/0020-0190(79)90069-3. SEÑOR  0552534.
7. de Berg, M .; van Kreveld, M .; Overmars, Marcos ; Schwarzkopf, O. (2008). Geometría computacional: algoritmos y aplicaciones (3ª ed.). Saltador. pag. 58.doi : 10.1007 /978-3-540-77974-2.
8. Meisters, GH (1975). "Los polígonos tienen oídos". El Mensual Matemático Estadounidense . 82 (6): 648–651. doi :10.2307/2319703. JSTOR  2319703. SEÑOR  0367792.
9. Hales, Thomas C. (2007). "Demostración de Jordan del teorema de la curva de Jordan" (PDF) . De la intuición a la prueba: Festschrift en honor a Andrzej Trybulec. Estudios de Lógica, Gramática y Retórica . 10 (23). Universidad de Białystok.
10. Thomassen, Carsten (1992). "El teorema de Jordan-Schönflies y la clasificación de superficies". El Mensual Matemático Estadounidense . 99 (2): 116-130. doi :10.1080/00029890.1992.11995820. JSTOR  2324180. SEÑOR  1144352.
11. Margalit, Avraham; Knott, Gary D. (1989). "Un algoritmo para calcular la unión, intersección o diferencia de dos polígonos". Computadoras y gráficos . 13 (2): 167–183. doi :10.1016/0097-8493(89)90059-9.
12. Niven, Iván ; Zuckerman, SA (1967). "Puntos de red y área poligonal". El Mensual Matemático Estadounidense . 74 (10): 1195-1200. doi :10.1080/00029890.1967.12000095. JSTOR  2315660. SEÑOR  0225216.
13. Aggarwal, Alok; Suri, Subhash (1990). "Calcular la diagonal más larga de un polígono simple". Cartas de procesamiento de información . 35 (1): 13-18. doi :10.1016/0020-0190(90)90167-V. SEÑOR  1069001.
14. Richmond, Bettina ; Richmond, Thomas (2023). Una transición discreta a las matemáticas avanzadas. Textos Puros y Aplicados de Pregrado. vol. 63 (2ª ed.). Sociedad Matemática Estadounidense. pag. 421.ISBN​ 9781470472047.
15. Snoeyink, Jack (1999). "Las razones cruzadas y los ángulos determinan un polígono". Geometría discreta y computacional . 22 (4): 619–631. doi : 10.1007/PL00009481 . SEÑOR  1721028.
16. Toussaint, Godfried (1991). "Polígonos antropomórficos". El Mensual Matemático Estadounidense . 98 (1): 31–35. doi :10.2307/2324033. JSTOR  2324033. SEÑOR  1083611.
17. Fisk, S. (1978). "Una breve prueba del teorema del vigilante de Chvátal". Revista de teoría combinatoria, serie B. 24 (3): 374. doi : 10.1016/0095-8956(78)90059-X .
18. Preparata, Franco P .; Supowit, Kenneth J. (1981). "Prueba de monotonicidad de un polígono simple". Cartas de procesamiento de información . 12 (4): 161–164. doi :10.1016/0020-0190(81)90091-0.
19. Schirra, Stefan (2008). "¿Qué tan confiables son las estrategias prácticas de punto en polígono?" (PDF) . En Halperin, Dan; Mehlhorn, Kurt (eds.). Algoritmos - ESA 2008, 16º Simposio Europeo Anual, Karlsruhe, Alemania, 15 al 17 de septiembre de 2008. Actas . Apuntes de conferencias sobre informática. vol. 5193. Saltador. págs. 744–755. doi :10.1007/978-3-540-87744-8_62.
20. Snoeyink, Jack (2017). "Ubicación del punto" (PDF) . En Toth, Csaba D.; O'Rourke, José; Goodman, Jacob E. (eds.). Manual de geometría discreta y computacional (3ª ed.). Chapman y Hall/CRC. págs. 1005-1023.
21. Braden, Bart (1986). "La fórmula del área del topógrafo" (PDF) . La revista universitaria de matemáticas . 17 (4): 326–337. doi :10.2307/2686282. JSTOR  2686282. Archivado desde el original (PDF) el 7 de noviembre de 2012.
22. Grünbaum, Branko ; Shephard, GC (febrero de 1993). "Teorema de Pick". El Mensual Matemático Estadounidense . 100 (2): 150–161. doi :10.2307/2323771. JSTOR  2323771. SEÑOR  1212401.
23. Chazelle, Bernard (1991). "Triangulación de un polígono simple en tiempo lineal". Geometría discreta y computacional . 6 (5): 485–524. doi : 10.1007/BF02574703 . SEÑOR  1115104.
24. Urrutia, Jorge (2000). "Galería de arte y problemas de iluminación". En Sack, Jörg-Rüdiger ; Urrutia, Jorge (eds.). Manual de geometría computacional . Ámsterdam: Holanda Septentrional. págs. 973-1027. doi :10.1016/B978-044482537-7/50023-1. ISBN 0-444-82537-1. SEÑOR  1746693.
25. Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alejandro (2015). "La distancia de inversión entre triangulaciones de un polígono simple es NP-completa". Geometría discreta y computacional . 54 (2): 368–389. arXiv : 1209.0579 . doi :10.1007/s00454-015-9709-7. SEÑOR  3372115.
26. Ahn, Hee-Kap; Barba, Luis; Bosé, Prosenjit ; De Carufel, Jean-Lou; Korman, Matías; Oh, Eunjin (2016). "Un algoritmo de tiempo lineal para el centro geodésico de un polígono simple". Geometría discreta y computacional . 56 (4): 836–859. arXiv : 1501.00561 . doi :10.1007/s00454-016-9796-0. SEÑOR  3561791.
27. Guibas, Leónidas ; Hershberger, John ; Leven, Daniel; Sharir, Micha ; Tarjan, Robert E. (1987). "Algoritmos de tiempo lineal para problemas de visibilidad y camino más corto dentro de polígonos simples triangulados". Algorítmica . 2 (2): 209–233. doi :10.1007/BF01840360. SEÑOR  0895445.
28. El Gindy, Hossam; Avis, David (1981). "Un algoritmo lineal para calcular el polígono de visibilidad desde un punto". Revista de algoritmos . 2 (2): 186–197. doi :10.1016/0196-6774(81)90019-5.
29. Chang, JS; Sí, C.-K. (1986). "Una solución polinómica para el problema del pelado de patatas". Geometría discreta y computacional . 1 (2): 155–182. doi : 10.1007/BF02187692 . SEÑOR  0834056.
30. Cabello, Sergio; Cibulka, Josef; Kynčl, Jan; Saumell, María; Valtr, Pavel (2017). "Pelar patatas de forma casi óptima en un tiempo casi lineal". Revista SIAM de Computación . 46 (5): 1574-1602. arXiv : 1406.1368 . doi :10.1137/16M1079695. SEÑOR  3708542.
31. Chin, Francisco YL ; Snoeyink, Jack; Wang, Cao An (1999). "Encontrar el eje medial de un polígono simple en tiempo lineal". Geometría discreta y computacional . 21 (3): 405–420. doi : 10.1007/PL00009429 . SEÑOR  1672988.
32. Cheng, Siu-Wing; Mencel, Liam; Vigneron, Antoine (2016). "Un algoritmo más rápido para calcular esqueletos rectos". Transacciones ACM sobre algoritmos . 12 (3): 44:1–44:21. arXiv : 1405.4691 . doi :10.1145/2898961.
33. Palfrader, Peter; Held, Martín (febrero de 2015). "Cálculo de curvas de desplazamiento en inglete basadas en esqueletos rectos". Diseño y aplicaciones asistidos por ordenador . 12 (4): 414–424. doi : 10.1080/16864360.2014.997637 .
34. Está bien, Eduardo; Sharir, Micha (2006). "Sumas de Minkowski de polígonos simples monótonos y generales". Geometría discreta y computacional . 35 (2): 223–240. doi : 10.1007/s00454-005-1206-y . SEÑOR  2195052.
35. Trefethen, Lloyd N .; Driscoll, Tobin A. (1998). "Mapeo de Schwarz-Christoffel en la era de la informática". Actas del Congreso Internacional de Matemáticos, vol. III (Berlín, 1998) . Documenta Matemática. págs. 533–542. SEÑOR  1648186.
36. Quintas, LV; Supnick, Fred (1965). "Sobre algunas propiedades de los circuitos hamiltonianos más cortos". El Mensual Matemático Estadounidense . 72 (9): 977–980. doi :10.2307/2313333. JSTOR  2313333. SEÑOR  0188872.
37. Demaine, Erik D .; Fekete, Sándor P.; Keldenich, Phillip; Krupke, Dominik; Mitchell, Joseph SB (2022). "Poligonalizaciones simples de área óptima: el desafío CG 2019". Revista ACM de algorítmica experimental . 27 : A2.4:1–12. doi :10.1145/3504000. hdl : 1721.1/146480 . SEÑOR  4390039.
38. Dobkin, David ; Guibas, Leónidas ; Hershberger, John ; Snoeyink, Jack (1993). "Un algoritmo eficaz para encontrar la representación CSG de un polígono simple". Algorítmica . 10 (1): 1–23. doi :10.1007/BF01908629. SEÑOR  1230699.
39. Ghosh, Subir Kumar; Goswami, Partha P. (2013). "Problemas no resueltos en gráficos de visibilidad de puntos, segmentos y polígonos". Encuestas de Computación ACM . 46 (2): 22:1–22:29. arXiv : 1012.5187 . doi :10.1145/2543581.2543589.

enlaces externos

• Weisstein, Eric W. "Polígono simple". MundoMatemático .