Problema de la galería de arte

Descripción del problema :

El Problema de la Galería de Arte se formula en geometría como el número mínimo de guardias que deben colocarse en un polígono simple de n vértices de manera que todos los puntos del interior sean visibles. Un polígono simple es una región cerrada conectada cuyo límite está definido por un número finito de segmentos de línea. Es una familia de problemas de visibilidad relacionados en geometría computacional. La visibilidad se define de tal manera que dos puntos u y v son mutuamente visibles si el segmento de línea que los une se encuentra dentro del polígono. Aquí, discutimos varias variantes. Los términos comunes utilizados en las variantes que se analizan a continuación:

• Un polígono P simple (no necesariamente convexo) para describir la galería de arte.
• Un conjunto de puntos S para describir los guardias donde cada guardia está representado por un punto en P.
• Una regla de que un punto A ∈ S puede proteger a otro punto B ∈ P si y solo si A ∈ S , B ∈ P y el segmento de línea AB está contenido en P.
• Una pregunta sobre si todos los puntos en el polígono P están protegidos por S .

Muchas variantes de este problema de la galería de arte se clasifican como problemas NP-difíciles . Aquí nos centraremos en las que admiten soluciones polinómicas:

• Variante 1: Determinar el límite superior del tamaño más pequeño del conjunto S .
• Variante 2: Determinar si ∃ un punto crítico C en el polígono P y ∃ otro punto D ∈ P tal que si el resguardo está en la posición C , el resguardo no puede proteger el punto D .
• Variante 3: Determine si el polígono P se puede proteger con una sola protección.
• Variante 4: determine el tamaño más pequeño del conjunto S si las protecciones solo pueden colocarse en los vértices del polígono P y solo los vértices deben protegerse.

Tenga en cuenta que hay muchas más variantes y al menos se ha escrito un libro para ello.

Soluciones :

1. La solución para la variante 1 es un trabajo teórico del teorema de la galería de arte de V´aclav Chv´atal . Afirma que [N/3] guardias siempre son suficientes y, a veces, necesarias para proteger un polígono simple con n vértices.
2. La solución para la variante 2 implica probar si el polígono P es cóncavo (y por lo tanto tiene un punto crítico). Podemos usar la negación de la función isConvex .
3. La solución para la variante 3 puede ser difícil si no se ha visto la solución antes. Podemos usar la función cortarPolígono . Cortamos el polígono P con todas las líneas formadas por los bordes en P en sentido contrario a las agujas del reloj y retenemos el lado izquierdo en todo momento. Si todavía tenemos un polígono no vacío al final, se puede colocar un protector en ese polígono no vacío que puede proteger todo el polígono P .
4. La solución para la variante 4 implica el cálculo de la cobertura mínima de vértices del ‘gráfico de visibilidad’ del polígono P . En general, este es otro problema NP-difícil .