Polígono en forma de estrella
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 se ve 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 zp 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, por lo que el diámetro del enlace del polígono (la distancia máxima de enlace en 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 kernel es 1 o 2; en este caso, la distancia máxima del enlace es 2.
Los antiparalelogramas y los hexágonos de Lemoine que se entrecruzan 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.
Probar si un polígono tiene forma de estrella y encontrar un solo punto en el núcleo se puede resolver en tiempo lineal formulando el problema como un programa lineal y aplicando técnicas para programación lineal de baja dimensión (ver http: //www.inf .ethz.ch / personal / emo / PublFiles / SubexLinProg_ALG16_96.pdf , página 16).
