IEICE TRANSACTIONS on Fundamentals
Chromatic Art Gallery Problem with r-Visibility is NP-Complete
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. 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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1108-1115
- Publication Date
- 2021/09/01
- Publicized
- 2021/03/26
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2020DMP0006
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Algorithms and Data Structures
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, "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
Copy
@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},}
Copy
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 -
English
