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. Nós estudamos um cromático variante do problema, onde cada guarda recebe um dos k cores distintas. Diz-se que uma proteção cromática é livre de conflitos se pelo menos uma das cores vistas por cada ponto P é único (ou seja, cada ponto em P é visto por algum guarda cuja cor aparece exatamente uma vez entre os guardas visíveis até aquele ponto). Neste artigo, consideramos vértice-a-ponto guarda, onde os guardas são colocados em vértices de P, e observam todos os pontos do interior de P. O Problema de galeria de arte cromática sem conflito de vértice a ponto é encontrar um conjunto de guardas coloridas tal que (i) as guardas sejam colocadas Pvértices de, e (ii) qualquer ponto em P pode ver um guarda de uma cor única entre todos os guardas visíveis. Neste artigo, é mostrado que determinar se existe um conjunto de proteção de vértice cromático livre de conflito para um polígono com buracos é 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, "Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 9, pp. 1499-1506, September 2023, doi: 10.1587/transinf.2022EDP7222.
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. A chromatic guarding is said to be conflict-free if at least one of the colors seen by every point in P is unique (i.e., each point in P is seen by some guard whose color appears exactly once among the guards visible to that point). In this paper, we consider vertex-to-point guarding, where the guards are placed on vertices of P, and they observe every point of the interior of P. The vertex-to-point conflict-free chromatic art gallery problem is to find a colored-guard set such that (i) guards are placed on P's vertices, and (ii) any point in P can see a guard of a unique color among all the visible guards. In this paper, it is shown that determining whether there exists a conflict-free chromatic vertex-guard set for a polygon with holes is NP-hard when the number of colors is k=2.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022EDP7222/_p
Copiar
@ARTICLE{e106-d_9_1499,
author={Chuzo IWAMOTO, Tatsuaki IBUSUKI, },
journal={IEICE TRANSACTIONS on Information},
title={Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem},
year={2023},
volume={E106-D},
number={9},
pages={1499-1506},
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. A chromatic guarding is said to be conflict-free if at least one of the colors seen by every point in P is unique (i.e., each point in P is seen by some guard whose color appears exactly once among the guards visible to that point). In this paper, we consider vertex-to-point guarding, where the guards are placed on vertices of P, and they observe every point of the interior of P. The vertex-to-point conflict-free chromatic art gallery problem is to find a colored-guard set such that (i) guards are placed on P's vertices, and (ii) any point in P can see a guard of a unique color among all the visible guards. In this paper, it is shown that determining whether there exists a conflict-free chromatic vertex-guard set for a polygon with holes is NP-hard when the number of colors is k=2.},
keywords={},
doi={10.1587/transinf.2022EDP7222},
ISSN={1745-1361},
month={September},}
Copiar
TY - JOUR
TI - Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem
T2 - IEICE TRANSACTIONS on Information
SP - 1499
EP - 1506
AU - Chuzo IWAMOTO
AU - Tatsuaki IBUSUKI
PY - 2023
DO - 10.1587/transinf.2022EDP7222
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2023
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. A chromatic guarding is said to be conflict-free if at least one of the colors seen by every point in P is unique (i.e., each point in P is seen by some guard whose color appears exactly once among the guards visible to that point). In this paper, we consider vertex-to-point guarding, where the guards are placed on vertices of P, and they observe every point of the interior of P. The vertex-to-point conflict-free chromatic art gallery problem is to find a colored-guard set such that (i) guards are placed on P's vertices, and (ii) any point in P can see a guard of a unique color among all the visible guards. In this paper, it is shown that determining whether there exists a conflict-free chromatic vertex-guard set for a polygon with holes is NP-hard when the number of colors is k=2.
ER -