Polígono 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 partes que consta de un número finito de segmentos de línea . Estos polígonos incluyen como casos especiales los polígonos convexos , los polígonos en forma de estrella y los polígonos monótonos .

La suma de los ángulos externos de un polígono simple es . Todo polígono simple con lados puede triangularse mediante sus diagonales y, por el teorema de la galería de arte, su interior es visible desde algunos de sus vértices. ${\estilo de visualización 2\pi}$ ${\estilo de visualización n}$ ${\estilo de visualización n-3}$ $\lpiso n/3\rpiso$

Los polígonos simples se consideran comúnmente como la entrada a problemas de geometría computacional , incluyendo pruebas de puntos en polígonos , cálculo de áreas , la envoltura convexa de un polígono simple , triangulación y 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 de geometría sólida constructiva para polígonos y gráficos de visibilidad de polígonos.

Definiciones

Un polígono simple es una curva cerrada en el plano euclidiano que consta de segmentos de línea recta que se unen por sus extremos para formar una cadena poligonal . ^[1] Dos segmentos de línea se unen en cada punto final y no hay otros puntos de intersección entre los segmentos de línea. Ningún subconjunto propio de los 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 línea que forman un polígono se denominan aristas o lados . Un punto final de un segmento se denomina 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 ; se pueden usar los términos más coloquiales lados y esquinas para evitar esta ambigüedad. ^[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 puntos finales 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 un polígono de este tipo 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 (enunciado 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 por 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 conexo no acotado , 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 abarcado 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 (un giro completo, 360°). Por lo tanto, la suma de los ángulos internos, para un polígono simple con lados es . ^[14] ${\estilo de visualización \pi}$ ${\estilo de visualización \pi}$ ${\estilo de visualización \theta}$ ${\estilo de visualización \pi -\theta}$ ${\estilo de visualización 2\pi}$ ${\estilo de visualización n}$ ${\estilo de visualización (n-2)\pi}$

Todo polígono simple puede dividirse en triángulos no superpuestos mediante un subconjunto de sus diagonales. Cuando el polígono tiene lados, esto produce triángulos, separados por diagonales. La partición resultante se denomina triangulación de polígonos . ^[8] La forma de un polígono simple triangulado puede determinarse de forma única mediante los ángulos internos del polígono y mediante las razones cruzadas de los cuadriláteros formados por pares de triángulos que comparten una diagonal. ^[15] ${\estilo de visualización n}$ ${\estilo de visualización n-2}$ ${\estilo de visualización 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 puntos extremos de una diagonal. ^[8] Un teorema relacionado establece que todo polígono simple que no sea un polígono convexo tiene una boca , un vértice cuyos dos vecinos son los puntos extremos de un segmento de línea que, de otro modo, es completamente exterior al polígono. Los polígonos que tienen exactamente dos orejas y una boca se denominan polígonos antropomorfos . ^[16]

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, pasando solo por puntos interiores del polígono. Una forma de demostrar esto es utilizar la 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 en 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 es utilizado por como máximo los vértices, lo que demuestra el teorema. ^[17] ${\estilo de visualización n}$ $\lpiso n/3\rpiso$ ${\estilo de visualización p}$ ${\estilo de visualización p}$ $\lpiso n/3\rpiso$

Casos especiales

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

Un polígono monótono , con respecto a una línea recta , es un polígono para el cual cada línea perpendicular a interseca el interior del polígono en un conjunto conexo. Equivalentemente, 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 a lo largo que en la cadena. ^[18] ${\estilo de visualización L}$ ${\estilo de visualización L}$ ${\estilo de visualización L}$ ${\estilo de visualización L}$

Problemas computacionales

Para comprobar si un punto está dentro del polígono, se construye un rayo que emane del punto y se cuentan sus intersecciones con el polígono. Si cruza sólo puntos interiores de las aristas, un número impar de veces, el punto se encuentra dentro del polígono; si es par, el punto se encuentra fuera. Los rayos que pasan por vértices de un polígono o que contienen sus aristas necesitan un cuidado especial. ^[19]

En geometría computacional , varias tareas computacionales importantes implican 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 en el interior de . Se puede resolver en tiempo lineal ; alternativamente, es posible procesar un polígono dado en una estructura de datos, en tiempo lineal, de modo que las pruebas de puntos en polígonos posteriores se puedan realizar en tiempo logarítmico. ^[20] ${\estilo de visualización P}$ ${\estilo de visualización q}$ ${\estilo de visualización q}$ ${\estilo de visualización P}$
Se conocen fórmulas sencillas para calcular el área del interior de un polígono. Entre ellas se encuentran 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 envoltura convexa de un polígono simple también se puede encontrar en tiempo lineal, más rápido que los algoritmos para encontrar envolturas convexas de puntos que no se han conectado 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 como máximo puntos, aunque no necesariamente utilizando el número óptimo de puntos para un polígono dado. ^[24] Aunque es posible transformar dos triangulaciones cualesquiera del mismo polígono entre sí mediante volteretas que reemplazan una diagonal a la vez, determinar si se puede hacer utilizando solo una cantidad limitada de volteretas es NP-completo . ^[25] $\lpiso n/3\rpiso$
Una ruta geodésica , ^[26] el camino más corto en el plano que conecta dos puntos interiores a un polígono, sin cruzar al exterior, se puede encontrar en tiempo lineal mediante un algoritmo que utiliza la triangulación como subrutina. ^[27] Lo mismo es cierto para el centro geodésico , un punto en el polígono que minimiza la longitud máxima de sus rutas geodésicas a 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 por segmentos de línea interiores al polígono, se pueden construir en tiempo lineal. ^[28] Lo mismo es cierto para el subconjunto que es visible desde al menos un punto de un segmento de línea dado. ^[27]

Otros problemas computacionales estudiados para polígonos simples incluyen construcciones de la diagonal más larga o el 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 la creación de características unidimensionales o puntos aislados. ^[11]

Construcciones relacionadas

Según el teorema de mapeo de Riemann , cualquier subconjunto abierto simplemente conectado del plano puede mapearse conformemente sobre 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 especificados e imágenes previas de los vértices del polígono en el límite del disco. Estos vértices previos se calculan normalmente numéricamente. ^[35]

Todo conjunto finito de puntos en el plano que no se encuentra sobre 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 viajante de comercio . ^[36] La conexión de puntos para formar un polígono de esta manera se denomina poligonalización . ^[37]

Todo 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 semiplano en la fórmula. La conversión de un polígono de lados a esta representación se puede realizar en tiempo . ^[38] ${\estilo de visualización n}$ $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 las 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 su gráfico de visibilidad, con un ciclo hamiltoniano especificado como su ciclo de lados, sigue siendo un problema abierto. ^[39]

Véase también

Problema de la regla del carpintero sobre el movimiento continuo de un polígono simple en un polígono convexo
Teorema de Erdős-Nagy , un proceso de reflexión de los bolsillos 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 maneras limitadas

Referencias

^ Milnor, John W. (1950). "Sobre la curvatura total de los nudos". Anales de Matemáticas . 2.ª serie. 52 : 248–257. doi :10.2307/1969467.
^ abcdef Preparata, Franco P. ; Shamos, Michael Ian (1985). Geometría computacional: una introducción. Textos y monografías en informática. Springer-Verlag. p. 18. doi :10.1007/978-1-4612-1098-6. ISBN 978-1-4612-1098-6.
^ ab 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. MR 1353288.
^ Aronov, 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 . MR 1222755.
^ Malkevitch, Joseph (2016). "¿Son una buena idea las definiciones precisas?". Columna destacada de la AMS . Sociedad Matemática Estadounidense.
^ ab McCallum, Duncan; Avis, David (1979). "Un algoritmo lineal para hallar la envoltura convexa de un polígono simple". Information Processing Letters . 9 (5): 201–206. doi :10.1016/0020-0190(79)90069-3. MR 0552534.
^ de Berg, M. ; van Kreveld, M. ; Overmars, Mark ; Schwarzkopf, O. (2008). Geometría computacional: algoritmos y aplicaciones (3.ª ed.). Springer. pág. 58. doi :10.1007/978-3-540-77974-2.
^ abc Meisters, GH (1975). "Los polígonos tienen orejas". The American Mathematical Monthly . 82 (6): 648–651. doi :10.2307/2319703. JSTOR 2319703. MR 0367792.
^ Hales, Thomas C. (2007). "La prueba de Jordan del teorema de la curva de Jordan" (PDF) . From Insight to Proof: Festschrift in Honour of Andrzej Trybulec. Estudios de lógica, gramática y retórica . 10 (23). Universidad de Bialystok.
^ Thomassen, Carsten (1992). "El teorema de Jordan-Schönflies y la clasificación de superficies". The American Mathematical Monthly . 99 (2): 116–130. doi :10.1080/00029890.1992.11995820. JSTOR 2324180. MR 1144352.
^ abcd Margalit, Avraham; Knott, Gary D. (1989). "Un algoritmo para calcular la unión, intersección o diferencia de dos polígonos". Computers & Graphics . 13 (2): 167–183. doi :10.1016/0097-8493(89)90059-9.
^ ab Niven, Ivan ; Zuckerman, HS (1967). "Puntos reticulares y área poligonal". The American Mathematical Monthly . 74 (10): 1195–1200. doi :10.1080/00029890.1967.12000095. JSTOR 2315660. MR 0225216.
^ ab Aggarwal, Alok; Suri, Subhash (1990). "Cálculo de la diagonal más larga de un polígono simple". Information Processing Letters . 35 (1): 13–18. doi :10.1016/0020-0190(90)90167-V. MR 1069001.
^ Richmond, Bettina ; Richmond, Thomas (2023). Una transición discreta a las matemáticas avanzadas. Textos universitarios puros y aplicados. Vol. 63 (2.ª ed.). Sociedad Matemática Estadounidense. pág. 421. ISBN 9781470472047.
^ 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 . MR 1721028.
^ Toussaint, Godfried (1991). "Polígonos antropomórficos". The American Mathematical Monthly . 98 (1): 31–35. doi :10.2307/2324033. JSTOR 2324033. MR 1083611.
^ Fisk, S. (1978). "Una breve demostración del teorema del vigilante de Chvátal". Journal of Combinatorial Theory, Serie B . 24 (3): 374. doi : 10.1016/0095-8956(78)90059-X .
^ Preparata, Franco P. ; Supowit, Kenneth J. (1981). "Prueba de monotonía en un polígono simple". Information Processing Letters . 12 (4): 161–164. doi :10.1016/0020-0190(81)90091-0.
^ Schirra, Stefan (2008). "¿Qué tan confiables son las estrategias prácticas de punto en polígono?" (PDF) . En Halperin, Dan; Mehlhorn, Kurt (eds.). Algorithms – ESA 2008, 16.° Simposio Europeo Anual, Karlsruhe, Alemania, 15-17 de septiembre de 2008. Actas . Lecture Notes in Computer Science. Vol. 5193. Springer. págs. 744-755. doi :10.1007/978-3-540-87744-8_62.
^ Snoeyink, Jack (2017). "Ubicación de puntos" (PDF) . En Toth, Csaba D.; O'Rourke, Joseph; Goodman, Jacob E. (eds.). Manual de geometría discreta y computacional (3.ª ed.). Chapman y Hall/CRC. págs. 1005–1023.
^ Braden, Bart (1986). "La fórmula del área del topógrafo" (PDF) . The College Mathematics Journal . 17 (4): 326–337. doi :10.2307/2686282. JSTOR 2686282. Archivado desde el original (PDF) el 7 de noviembre de 2012.
^ Grünbaum, Branko ; Shephard, GC (febrero de 1993). "Teorema de Pick". The American Mathematical Monthly . 100 (2): 150–161. doi :10.2307/2323771. JSTOR 2323771. MR 1212401.
^ 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 . MR 1115104.
^ Urrutia, Jorge (2000). "Galería de arte y problemas de iluminación". En Sack, Jörg-Rüdiger ; Urrutia, Jorge (eds.). Handbook of Computational Geometry . Ámsterdam: Holanda Septentrional. pp. 973–1027. doi :10.1016/B978-044482537-7/50023-1. ISBN 0-444-82537-1.Señor 1746693 .
^ Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alexander (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. MR 3372115.
^ ab Ahn, Hee-Kap; Barba, Luis; Bose, Prosenjit ; De Carufel, Jean-Lou; Korman, Matias; 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. MR 3561791.
^ ab Guibas, Leonidas ; Hershberger, John ; Leven, Daniel; Sharir, Micha ; Tarjan, Robert E. (1987). "Algoritmos de tiempo lineal para problemas de visibilidad y ruta más corta dentro de polígonos simples triangulados". Algorithmica . 2 (2): 209–233. doi :10.1007/BF01840360. MR 0895445.
^ El Gindy, Hossam; Avis, David (1981). "Un algoritmo lineal para calcular el polígono de visibilidad a partir de un punto". Journal of Algorithms . 2 (2): 186–197. doi :10.1016/0196-6774(81)90019-5.
^ Chang, JS; Yap, C.-K. (1986). "Una solución polinómica para el problema de pelar patatas". Geometría discreta y computacional . 1 (2): 155–182. doi : 10.1007/BF02187692 . MR 0834056.
^ Cabello, Sergio; Cibulka, Josef; Kynčl, Jan; Saumell, Maria; 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. MR 3708542.
^ Chin, Francis 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 . MR 1672988.
^ Cheng, Siu-Wing; Mencel, Liam; Vigneron, Antoine (2016). "Un algoritmo más rápido para calcular esqueletos rectos". ACM Transactions on Algorithms . 12 (3): 44:1–44:21. arXiv : 1405.4691 . doi :10.1145/2898961.
^ Palfrader, Peter; Held, Martin (febrero de 2015). "Cálculo de curvas de desplazamiento en inglete basadas en esqueletos rectos". Diseño asistido por ordenador y aplicaciones . 12 (4): 414–424. doi : 10.1080/16864360.2014.997637 .
^ Oks, Eduard; Sharir, Micha (2006). "Sumas de Minkowski de polígonos monótonos y simples generales". Geometría discreta y computacional . 35 (2): 223–240. doi : 10.1007/s00454-005-1206-y . MR 2195052.
^ 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 Mathematica. págs. 533–542. MR 1648186.
^ Quintas, LV; Supnick, Fred (1965). "Sobre algunas propiedades de los circuitos hamiltonianos más cortos". The American Mathematical Monthly . 72 (9): 977–980. doi :10.2307/2313333. JSTOR 2313333. MR 0188872.
^ Demaine, Erik D .; Fekete, Sándor P.; Keldenich, Phillip; Krupke, Dominik; Mitchell, Joseph SB (2022). "Polinealizaciones simples óptimas en cuanto al área: el desafío CG 2019". ACM Journal of Experimental Algorithmics . 27 : A2.4:1–12. doi :10.1145/3504000. hdl : 1721.1/146480 . MR 4390039.
^ Dobkin, David ; Guibas, Leonidas ; Hershberger, John ; Snoeyink, Jack (1993). "Un algoritmo eficiente para encontrar la representación CSG de un polígono simple". Algorithmica . 10 (1): 1–23. doi :10.1007/BF01908629. MR 1230699.
^ 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 de ACM . 46 (2): 22:1–22:29. arXiv : 1012.5187 . doi :10.1145/2543581.2543589.

Enlaces externos

Weisstein, Eric W. "Polígono simple". MathWorld .