Polígono con forma de estrella

En geometría, un polígono en forma de estrella es un polígono plano que es un dominio en estrella, es decir, un polígono que contiene un punto a partir del cual todo el límite del polígono es visible.

Un polígono en forma de estrella (arriba). Su núcleo se muestra en la parte inferior en rojo

Formalmente, un polígono $P$ tiene forma de estrella si existe al menos un punto $z$ tal que para cada punto $p$ de $P$ el segmento ${\overline {zp}}$ se encuentre completamente dentro de $P$ .^[1] El conjunto de todos los puntos $z$ con esta propiedad (es decir, el conjunto de puntos desde los cuales todo $P$ es visible) se denomina núcleo de $P$ .

Si un polígono en forma de estrella es convexo, la distancia de enlace entre dos de sus puntos (el número mínimo de segmentos de línea secuenciales suficientes para conectar esos puntos) es 1, por lo que el diámetro de enlace del polígono (la distancia máxima de enlace sobre todos los pares de puntos) es 1. Si un polígono en forma de estrella no es convexo, la distancia de enlace entre un punto en el núcleo y cualquier otro punto en el polígono es 1, mientras que la distancia de enlace entre dos puntos cualesquiera que están en el polígono pero fuera del núcleo es 1 o 2; en este caso, la distancia máxima del enlace es 2.

Ejemplos

Los polígonos convexos tienen forma de estrella y un polígono convexo coincide con su propio núcleo.
Las estrellas regulares tienen forma de estrella y su centro siempre está en el núcleo.
Los antiparalelogramos y los hexágonos de Lemoine, figuras que se intersecan a sí mismas, tienen forma de estrella y el núcleo consta de un solo punto.
Los polígonos de visibilidad tienen forma de estrella, ya que cada punto dentro de ellos debe ser visible desde el centro por definición.

Algoritmos

Probar si un polígono tiene forma de estrella y encontrar un único punto en el núcleo se puede resolver en tiempo lineal formulando el problema como un caso de programación lineal, y consecuentemente, aplicando técnicas de programación lineal de baja dimensión (véase http://www.inf.ethz .ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf, página 16).

Cada arista de un polígono define un semiplano interior, el semiplano cuyo límite se encuentra en la línea recta que contiene la arista y que contiene los puntos del polígono en un entorno de cualquier punto interior de la arista. El núcleo de un polígono es la intersección de todos sus semiplanos interiores. La intersección de un conjunto arbitrario de N semiplanos se puede encontrar en tiempo Θ(N log N) utilizando el algoritmo conocido como divide y vencerás.^[1] Sin embargo, para el caso de núcleos de polígonos, es posible un método más rápido: Lee y Preparata (1979)^[2] presentaron un algoritmo para construir el núcleo en tiempo lineal.

Véase también

Polígono monótono

Referencias

↑ ^a ^b Franco P. Preparata y Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer Science+Business Media. ISBN 0-387-96131-3. 1ª edición: ; 2ª edición, corregida y ampliada, 1988.
↑ Lee, D. T.; Preparata, F. P. (July 1979), «An Optimal Algorithm for Finding the Kernel of a Polygon», Journal of the ACM 26 (3): 415-421, S2CID 6156190, doi:10.1145/322139.322142, hdl:2142/74090, archivado desde el original el 24 de septiembre de 2017 .

Datos: Q2122886
Multimedia: Star shape / Q2122886

[PS-1] Franco P. Preparata y Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer Science+Business Media. ISBN 0-387-96131-3. 1ª edición: ; 2ª edición, corregida y ampliada, 1988.

[2] Lee, D. T.; Preparata, F. P. (July 1979), «An Optimal Algorithm for Finding the Kernel of a Polygon», Journal of the ACM 26 (3): 415-421, S2CID 6156190, doi:10.1145/322139.322142, hdl:2142/74090, archivado desde el original el 24 de septiembre de 2017 .

[1]

[2]