Variantes da galeria de arte com visibilidade aos pares?

O problema tradicional da galeria de arte configura uma região e os guardas com alguma noção de visibilidade e solicita o número mínimo de guardas que precisam ser colocados para ver toda a região.

Alguém já olhou as variantes da galeria de arte em que a região de visibilidade é definida por um par de guardas. Por exemplo, uma formulação pode ser a de que um ponto é coberto se houver um par de guardas cujo disco delimitador mínimo o cubra?

reference-request cg.comp-geom Suresh Venkat
fonte

Quis custodiet ipsos custodes?

Artem Kaznatcheev

Bem, para responder à pergunta de @ Artem, existe uma noção de guardas conectados , que tem duas variantes. Deixe o gráfico de visibilidade ser definido com um vértice para cada guarda e uma aresta entre dois vértices, se os guardas puderem se ver. Se o gráfico de visibilidade estiver conectado, todos os guardas serão protegidos (às vezes chamado de "conjunto de guardas protegidos"). Uma condição mais forte é que o gráfico de visibilidade tenha um único componente conectado. Então você tem um conjunto de guardas conectados. E sim, há uma quantidade razoável de trabalho aqui. Eu até escrevi sobre um artigo.

Aaron Sterling

Whoops, o acima deve ler "se o gráfico a visibilidade não foi isolado vértices, todos os guardas são guardados ..."

Aaron Sterling

"quem guarda os guardas"? minha Latina é de apenas porco :)

Suresh Venkat

Observe que, na minha formulação, não exijo que o gráfico de visibilidade induzido esteja conectado. Embora isso possa não ser um problema com retângulos paralelos aos eixos, na verdade pode ser um problema com regiões que não são tão agradáveis (como regiões elípticas). Mas o ponteiro dos guardas conectados é bom: acho que provavelmente algumas variantes do meu problema podem ser tratadas dessa maneira.

Suresh Venkat

Respostas:

Não conheço esse trabalho. No entanto, eu esperaria que esse problema fosse NP-completo e, para polígonos com orifícios, seria tão difícil de aproximar quanto Definir Capa. O problema relativamente simples de proteção de vértices / vértices, no qual as proteções só podem se apoiar em vértices e somente os vértices precisam ser protegidos, é difícil ( Eidenbenz, Stamm e Widmayer (2001) ).

Para polígonos simples, espero que esse problema seja:

NP-completo
APX-hard
Aproximado para dentro de um fator de , em que opt é o número ideal de proteções. $O(\log(\rm{opt}))$

O problema de proteção de vértices / vértices é difícil para APX em polígonos simples ( Eidenbenz (1998) ).

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

Pensei um pouco sobre esse problema na minha tese, mas cheguei à opinião de que não havia variantes particularmente interessantes que não parecessem reduzir bastante de perto a um problema conhecido que envolvia guarda única.

James King
fonte

Bastante tarde para esta pergunta (desculpe!). Há pelo menos um pouco de trabalho.

(1) Este parece ser um trabalho de pesquisa de graduação (Swarthmore): "Ótima cobertura dupla na galeria de arte", Scott Dalane, Andrew Frampton, 2008, link em PDF . Da conclusão deles:

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

$\lfloor 2n/3 \rfloor$

Joseph O'Rourke
fonte

Então, eu estive pensando sobre isso. Eu acho que a principal diferença entre a cobertura dupla e o meu problema é que existe esse problema de "conexão". Em outras palavras, nenhuma das regiões de visibilidade dos dois guardas é ativada, a menos que sejam "visíveis" um para o outro. É fácil criar exemplos em que você pode cobrir uma região com guardas que não se veem. Agora, o problema de guardas conectados também foi analisado, mas em um contexto diferente que novamente não se aplica aqui - especificamente lá, é necessário que o gráfico de visibilidade de guardas esteja conectado, e eu não preciso disso.

Suresh Venkat

p

$p$

p

$p$

p

$p$

Nem tanto. não é pura visibilidade. Um par de guardas define uma "região de visibilidade" e um ponto é coberto se estiver na região de visibilidade dos guardas. De fato, é possível para os guardas que não conseguem se ver OU o ponto no sentido tradicional da "linha de visão" para "encobrir" o ponto.

Suresh Venkat

Obrigado por esclarecer. Este modelo parece diferente de tudo o que sei.

Joseph O'Rourke