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}$${\displaystyle \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.

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]

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}$ ${\displaystyle \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 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 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}$${\displaystyle \lpiso n/3\rpiso}$${\estilo de visualización p}$${\estilo de visualización p}$${\displaystyle \lpiso n/3\rpiso}$

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}$

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 en otra 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]${\displaystyle \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, puede encontrarse 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]

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 típicamente 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}$${\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 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]

• 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

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