En geometría , un polígono en forma de estrella es una región poligonal en el plano que es un dominio de estrella , es decir, un polígono que contiene un punto desde el cual es visible todo el límite del polígono .
Formalmente, un polígono P tiene forma de estrella si existe un punto z tal que para cada punto p de P el segmento se encuentra 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 llama 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, y por lo tanto el diámetro de enlace del polígono (la distancia de enlace máxima 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 de enlace máxima es 2.
Los polígonos convexos tienen forma de estrella y un polígono convexo coincide con su propio núcleo.
Los polígonos estrellados regulares tienen forma de estrella, con su centro siempre en el núcleo.
Los antiparalelogramos y los hexágonos de Lemoine autointersecantes tienen forma de estrella, y su núcleo consiste en un solo punto.
Los polígonos de visibilidad tienen forma de estrella, ya que cada punto dentro de ellos debe ser visible para el centro por definición.
Para comprobar si un polígono tiene forma de estrella y encontrar un único punto en el núcleo, se puede formular el problema como un programa lineal y aplicar 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 borde de un polígono define un semiplano interior , el semiplano cuyo límite se encuentra en la línea que contiene el borde y que contiene los puntos del polígono en un vecindario de cualquier punto interior del borde. 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 Θ ( N log N ) tiempo utilizando el enfoque de 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 & Preparata (1979) [2] presentaron un algoritmo para construir el núcleo en tiempo lineal.
