Me pregunto sobre el siguiente problema: Dado un polígono y el conjunto de puntos $S$ en su interior, ¿cuáles son los puntos en $S$ de la cual la mayor parte del área en $S$ es visible? Además, ¿cuál es la superficie máxima visible?
Aquí, defino $q$ para ser visible desde $p$ si el segmento de línea entre $p$ y $q$ está contenida en $S$ . Con ello se pretende captar la idea intuitiva de qué puntos de una habitación son visibles cuando se está en algún lugar de la misma. Por ejemplo, en la figura siguiente, el área azul oscuro es visible desde el punto P, en el centro del cuarto superior izquierdo. El área azul claro no lo es.
Mientras que la respuesta para cualquier dominio con forma de estrella está clara, encontrar la respuesta para polígonos arbitrarios parece difícil.
Pregunta: ¿Cómo podemos encontrar la solución del problema para un polígono dado?
Por ejemplo, el problema no es tan fácil para el polígono de abajo... 
0 votos
Esta es una pregunta muy bonita. Mis "respuestas" a continuación no la responden. Podría ser NP-difícil.
0 votos
Aunque el problema de la Galería de Arte es NP-Duro, no creo que este lo sea. El polígono de visibilidad a partir de un punto puede ser pensado dualmente como el lápiz de segmentos de línea. Esto, a su vez, se asigna a un "círculo" en el complejo de visibilidad (cf. Michel Pocchiola 1993 o 1996). Así, el área del polígono es la integral de las longitudes de los segmentos a lo largo del complejo. Creo que buscar el máximo será como resolver un sistema de ecuaciones lineales. Una advertencia: no sé cómo es el espacio de puntos (es decir, los "círculos" de lápiz de segmento) en el complejo de visibilidad, o si se subdivide tan bien como creo que lo hace.