Polígono con forma de estrella

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

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.

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.

[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.