A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Chromatic Art Gallery Problem with r-Visibility is NP-Complete Problema da galeria de arte cromática com r-Visibilidade é NP-Completa

Chuzo IWAMOTO, Tatsuaki IBUSUKI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

O problema da galeria de arte é encontrar um conjunto de guardas que juntos possam observar todos os pontos do interior de um polígono P. Estudamos uma variante cromática do problema, onde a cada guarda é atribuído um dos k cores distintas. O problema da galeria de arte cromática é encontrar um guarda definido para P de modo que não haja duas proteções da mesma cor com regiões de visibilidade sobrepostas. Estudamos a versão de decisão deste problema para polígonos ortogonais com r-visibilidade quando o número de cores é k=2. Aqui, dois pontos são r-visível se o menor retângulo alinhado ao eixo que os contém estiver inteiramente dentro do polígono. Neste artigo, é mostrado que determinar se existe uma r-guarda de visibilidade definida para um polígono ortogonal com buracos de modo que não haja duas guardas com a mesma cor com regiões de visibilidade sobrepostas é NP-difícil quando o número de cores é k= 2.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1108-1115
Data de publicação
2021/09/01
Publicitada
2021/03/26
ISSN online
1745-1337
DOI
10.1587/transfun.2020DMP0006
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria
Algoritmos e estruturas de dados

autores

Chuzo IWAMOTO
  Hiroshima University
Tatsuaki IBUSUKI
  Hiroshima University

Palavra-chave