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
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.
Chuzo IWAMOTO
Hiroshima University
Tatsuaki IBUSUKI
Hiroshima University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Chuzo IWAMOTO, Tatsuaki IBUSUKI, "Chromatic Art Gallery Problem with r-Visibility is NP-Complete" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 9, pp. 1108-1115, September 2021, doi: 10.1587/transfun.2020DMP0006.
Abstract: The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. The chromatic art gallery problem is to find a guard set for P such that no two guards with the same color have overlapping visibility regions. We study the decision version of this problem for orthogonal polygons with r-visibility when the number of colors is k=2. Here, two points are r-visible if the smallest axis-aligned rectangle containing them lies entirely within the polygon. In this paper, it is shown that determining whether there is an r-visibility guard set for an orthogonal polygon with holes such that no two guards with the same color have overlapping visibility regions is NP-hard when the number of colors is k=2.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020DMP0006/_p
Copiar
@ARTICLE{e104-a_9_1108,
author={Chuzo IWAMOTO, Tatsuaki IBUSUKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Chromatic Art Gallery Problem with r-Visibility is NP-Complete},
year={2021},
volume={E104-A},
number={9},
pages={1108-1115},
abstract={The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. The chromatic art gallery problem is to find a guard set for P such that no two guards with the same color have overlapping visibility regions. We study the decision version of this problem for orthogonal polygons with r-visibility when the number of colors is k=2. Here, two points are r-visible if the smallest axis-aligned rectangle containing them lies entirely within the polygon. In this paper, it is shown that determining whether there is an r-visibility guard set for an orthogonal polygon with holes such that no two guards with the same color have overlapping visibility regions is NP-hard when the number of colors is k=2.},
keywords={},
doi={10.1587/transfun.2020DMP0006},
ISSN={1745-1337},
month={September},}
Copiar
TY - JOUR
TI - Chromatic Art Gallery Problem with r-Visibility is NP-Complete
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1108
EP - 1115
AU - Chuzo IWAMOTO
AU - Tatsuaki IBUSUKI
PY - 2021
DO - 10.1587/transfun.2020DMP0006
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2021
AB - The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. The chromatic art gallery problem is to find a guard set for P such that no two guards with the same color have overlapping visibility regions. We study the decision version of this problem for orthogonal polygons with r-visibility when the number of colors is k=2. Here, two points are r-visible if the smallest axis-aligned rectangle containing them lies entirely within the polygon. In this paper, it is shown that determining whether there is an r-visibility guard set for an orthogonal polygon with holes such that no two guards with the same color have overlapping visibility regions is NP-hard when the number of colors is k=2.
ER -