¿Variantes de la galería de arte con visibilidad por pares?

El problema de la galería de arte tradicional establece una región y guardias con alguna noción de visibilidad, y solicita el número mínimo de guardias que deben colocarse para ver toda la región.

¿Alguien ha mirado alguna vez las variantes de la galería de arte donde la región de visibilidad está definida por un par de guardias? Por ejemplo, una formulación podría ser que un punto está cubierto si hay un par de guardias cuyo disco límite mínimo lo cubre.

reference-request cg.comp-geom Suresh Venkat
fuente

Quis custodiet ipsos custodes?

Artem Kaznatcheev

Bueno, para responder a la pregunta de @ Artem, hay una noción de guardias conectados , que tiene dos variantes. Deje que el gráfico de visibilidad se defina con un vértice para cada guardia y un borde entre dos vértices si los guardias pueden verse entre sí. Si el gráfico de visibilidad está conectado, todos los guardias están protegidos (a veces llamado "conjunto de guardias protegidos"). Una condición más fuerte es que el gráfico de visibilidad tiene un solo componente conectado. Entonces tienes un conjunto de guardias conectados. Y sí, hay una buena cantidad de trabajo aquí. Incluso he blogueado sobre un artículo.

Aaron Sterling

Vaya, lo anterior debería leer "si el gráfico de visibilidad no tiene vértices aislados, todos los guardias están vigilados ..."

Aaron Sterling

"¿Quién guarda a los guardias"? mi latín es solo cerdo :)

Suresh Venkat

Tenga en cuenta que en mi formulación, no necesito que se conecte el gráfico de visibilidad inducida. Si bien esto podría no ser un problema con los rectángulos paralelos al eje, en realidad podría ser un problema con las regiones que no son tan agradables (como las regiones elípticas). Pero el puntero de los guardias conectados es bueno: creo que probablemente algunas variantes de mi problema pueden abordarse de esa manera.

Suresh Venkat

Respuestas:

No estoy al tanto de tal trabajo. Sin embargo, esperaría que tal problema fuera NP completo y, para los polígonos con agujeros, sería tan difícil de aproximar como Set Cover. El problema relativamente sencillo de protección de vértices / vértices, en el que los guardias solo pueden descansar en los vértices y solo los vértices deben protegerse, es tan difícil ( Eidenbenz, Stamm y Widmayer (2001) ).

Para polígonos simples, espero que tal problema sea:

NP-complete
APX-hard
$O(\log(\rm{opt}))$

El problema de protección de vértice / vértice es difícil de APX para polígonos simples ( Eidenbenz (1998) ).

$\varepsilon$ $O(\log(\rm{opt}))$

Pensé un poco en este problema para mi tesis, pero llegué a la opinión de que no había variantes particularmente interesantes que no parecieran reducirse bastante a un problema conocido relacionado con la protección individual.

James King
fuente

Más bien tarde a esta pregunta (¡lo siento!). Hay al menos un poco de trabajo.

(1) Esto parece ser un trabajo de investigación de pregrado (Swarthmore): "Cobertura doble óptima en la galería de arte", Scott Dalane, Andrew Frampton, 2008, enlace PDF . De su conclusión:

$\lfloor 2n/3 \rfloor$ $n^2$

$\lfloor 2n/3 \rfloor$

Joseph O'Rourke
fuente

Así que he estado pensando en esto. Creo que la principal diferencia entre la doble cobertura y mi problema es que existe este problema de "conectividad". En otras palabras, ninguna de las regiones de visibilidad de los dos guardias se activa a menos que sean "visibles" entre sí. Es fácil construir ejemplos en los que puedes cubrir una región de forma doble con guardias que no se ven. Ahora, el problema de los guardias conectados TAMBIÉN se ha analizado, pero en un contexto diferente que nuevamente no se aplica aquí, específicamente allí, se requiere que el gráfico de visibilidad del guardia esté conectado, y no lo necesito.

Suresh Venkat

p

$p$

p

$p$

p

$p$

No exactamente. No es pura visibilidad. Un par de guardias define una "región de visibilidad" y un punto está cubierto si se encuentra en la región de visibilidad de los guardias. De hecho, es posible que los guardias que no se puedan ver O el punto en el sentido tradicional de "línea de visión" "cubran" el punto.

Suresh Venkat

Gracias por aclararlo. Este modelo parece diferente de todo lo que sé.

Joseph O'Rourke