Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem

Chuzo IWAMOTO; Tatsuaki IBUSUKI

doi:10.1587/transinf.2022EDP7222

Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem

Chuzo IWAMOTO, Tatsuaki IBUSUKI

Full Text Views

0

Cite this

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

chromatic art gallery problem, polygons, visibility, NP-hard

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 -