Polígono simple

En geometría , un polígono simple es aquel que no se interseca a sí mismo y no tiene agujeros. Es decir, es una curva de Jordan lineal a trozos compuesta por un número finito de segmentos de línea . 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${\displaystyle 2\pi }$. Cada polígono simple con${\displaystyle n}$Los lados pueden ser triangulados por${\displaystyle n-3}$de sus diagonales, y por el teorema de la galería de arte su interior es visible desde algunos${\displaystyle \lfloor n/3\rfloor }$de sus vértices.

Los polígonos simples se utilizan habitualmente como entrada para 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 rutas euclidianas más cortas .

Otras construcciones geométricas relacionadas con polígonos simples incluyen el mapeo de Schwarz-Christoffel , utilizado para encontrar transformaciones conformes que involucran polígonos simples, la poligonizació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 formada por segmentos de línea recta que se unen extremo con extremo para formar una cadena poligonal . ^{[ 1 ]} Dos segmentos de línea se encuentran en cada extremo, y no hay otros puntos de intersección entre los segmentos. Ningún subconjunto propio de los segmentos tiene las mismas propiedades. ^{[ 2 ]} A veces se omite el calificativo «simple» , asumiendo que la palabra «polígono» se refiere a un polígono simple. ^{[ 3 ]}

Los segmentos de línea que forman un polígono se denominan aristas o lados . Un extremo de un segmento se denomina vértice (plural: vértices) ^{[ 2 ]} o esquina . Aristas y vértices son términos más formales, pero pueden resultar ambiguos en contextos que también involucran las aristas y los vértices de un grafo ; para evitar esta ambigüedad, se pueden usar 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 lo prohíben, requiriendo en cambio que los segmentos colineales de una cadena poligonal cerrada se fusionen en un único 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 demostración original de este teorema por Camille Jordan tomó como punto de partida el caso especial de los polígonos simples (enunciado sin demostración). ^{[ 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 no nula . ^{[ 11 ]} El polígono mismo 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 suele ser 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 sus extremos 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 formado por el interior del polígono en ese vértice. Un vértice es convexo si su ángulo interno es menor que${\displaystyle \pi }$(un ángulo recto, 180°) y cóncava si el ángulo interno es mayor que${\displaystyle \pi }$. Si el ángulo interno es${\displaystyle \theta }$, el ángulo externo en el mismo vértice se define como su suplemento${\displaystyle \pi -\theta }$, 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${\displaystyle 2\pi }$(una vuelta completa, 360°). Por lo tanto, la suma de los ángulos internos, para un polígono simple con${\displaystyle n}$lados es${\displaystyle (n-2)\pi }$. ^{[ 14 ]}

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

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 convexo tiene una boca , un vértice cuyos dos vecinos son los extremos 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 denominan polígonos antropomórficos . ^{[ 16 ]}

Según el teorema de la galería de arte , en un polígono simple con${\displaystyle n}$vértices, siempre es posible encontrar un subconjunto de como máximo${\displaystyle \lfloor n/3\rfloor }$de 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${\displaystyle p}$En el polígono, existe un segmento de línea que conecta${\displaystyle p}$a un vértice seleccionado, pasando solo por puntos interiores del polígono. Una forma de demostrar esto es usar la coloración de grafos 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 extremos de colores diferentes. 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${\displaystyle \lfloor n/3\rfloor }$de los vértices, demostrando el teorema. ^{[ 17 ]}

Todo polígono convexo es un polígono simple. Otra clase importante de polígonos simples son los polígonos estrellados , que tienen un punto (en su interior o en su borde) desde el cual se puede ver cualquier otro punto. ^{[ 2 ]}

Un polígono monótono , con respecto a una línea recta.${\displaystyle L}$, es un polígono para el cual toda línea perpendicular a${\displaystyle L}$interseca el interior del polígono en un conjunto conexo. Equivalentemente, es un polígono cuyo límite puede dividirse en dos cadenas poligonales monótonas, subsecuencias de aristas cuyos vértices, cuando se proyectan perpendicularmente sobre${\displaystyle L}$, tienen el mismo orden a lo largo${\displaystyle L}$como lo hacen en la cadena. ^{[ 18 ]}

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

• En las pruebas de polígonos, el punto implica determinar, para un polígono simple,${\displaystyle P}$y un punto de consulta${\displaystyle q}$, si${\displaystyle q}$se encuentra en el interior de${\displaystyle P}$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 subsiguientes de puntos en el polígono se puedan realizar en tiempo logarítmico. ^{[ 20 ]}
• Se conocen fórmulas sencillas para calcular el área del interior de un polígono. Estas 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 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 para formar 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. Una modificación del mismo algoritmo también se puede utilizar para comprobar si una cadena poligonal cerrada forma un polígono simple (es decir, si evita 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${\displaystyle \lfloor n/3\rfloor }$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 una en la otra mediante giros que reemplazan una diagonal a la vez, determinar si se puede hacer utilizando solo un número limitado de giros es NP-completo . ^{[ 25 ]}
• Una trayectoria geodésica , ^{[ 26 ]} la trayectoria más corta en el plano que conecta dos puntos interiores a un polígono, sin cruzar al exterior, puede hallarse 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 trayectorias geodésicas a todos los demás puntos. ^{[ 26 ]}
• El polígono de visibilidad de un punto interior de un polígono simple, es decir, los puntos que son directamente visibles desde el punto dado mediante segmentos de línea interiores al polígono, puede construirse en tiempo lineal. ^{[ 28 ]} Lo mismo ocurre con 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 dentro de 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 aproximan su forma, incluyendo 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 manera que siempre produzcan 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 conexo del plano puede mapearse conformemente sobre un disco. El mapeo de Schwarz-Christoffel proporciona un método para construir explícitamente un mapeo de un disco a cualquier polígono simple utilizando ángulos de vértice específicos y preimágenes de los vértices del polígono en el borde del disco. Estos prevértices se calculan típicamente de forma numérica. ^{[ 35 ]}

Todo conjunto finito de puntos en el plano que no se encuentra sobre una sola línea puede conectarse para formar los vértices de un polígono simple (permitiendo ángulos de 180°); por ejemplo, uno de estos polígonos es la solución al problema del viajante . ^{[ 36 ]} Conectar puntos para formar un polígono de esta manera se denomina poligonizació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 , apareciendo cada lado del polígono una vez como un semiplano en la fórmula. Convertir un${\displaystyle n}$El polígono de lados en esta representación se puede realizar en tiempo${\displaystyle O(n\log n)}$. ^{[ 38 ]}

El grafo 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 grafo dado como su grafo 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 hacia un polígono convexo.
• Teorema de Erdős-Nagy , un proceso de reflexión de cavidades 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 dado.
• Polígono esférico , un concepto análogo en la superficie de una esfera.
• Polígono débilmente simple , una generalización de los polígonos simples que permite que los bordes se toquen de forma limitada.

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