The search functionality is under construction.

The search functionality is under construction.

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

- 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

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.

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

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

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

ER -