IEICE TRANSACTIONS on Information
Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E106-D No.9 pp.1499-1506
- Publication Date
- 2023/09/01
- Publicized
- 2023/05/31
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2022EDP7222
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Chuzo IWAMOTO
Hiroshima University
Tatsuaki IBUSUKI
Hiroshima University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
