Computational Complexity of the r-visibility Guard Set Problem for Polyominoes - Discrete and Computational Geometry and Graphs - page 87

Computational Complexity of the -visibility

Guard Set Problem for Polyominoes

r

B

Chuzo Iwamoto (

) and Toshihiko Kume

Graduate School of Engineering, Hiroshima University,
Higashi-Hiroshima 739-8527, Japan
[e-mail]

Abstract. We study the art gallery problem when the instance is a
polyomino, which is the union of connected unit squares. It is shown that
locating the minimum number of guards with r -visibility in a polyomino
with holes is NP-hard. Here, two points u and v on a polyomino are
r-visible if the orthogonal bounding rectangle for u and v lies entirely

within the polyomino. As a corollary, locating the minimum number of
guards with r -visibility in an orthogonal polygon with holes is NP-hard.

· · r -visibility ·

Keywords: Art gallery problem Polyomino NP-hard

1 Introduction

The art gallery problem is to determine the minimum number of guards who
can observe the interior of a gallery. Chvatal [ 4 ] proved that n/ 3 guards are

the lower and upper bounds for this problem; namely, guards are always

sucient and sometimes necessary for observing the interior of an

n/ 3

n -vertex sim-

ple polygon. This n/ 3 -bound is replaced by n/ 4 if the instance is restricted

to a simple orthogonal polygon [ 7 ].
Another approach to the art gallery problem is to study the complexity of
locating the minimum number of guards in a polygon. The NP-hardness and
APX-hardness of this problem were shown by Lee and Lin [ 9 ] and by Eidenbenz
et al. [ 5 ], respectively. Furthermore, Schuchardt and Hecker [ 13 ] proved that
this problem remains NP-hard if we restrict our attention to simple orthogonal
polygons. Even guarding the vertices of a simple orthogonal polygon was shown
to be NP-hard [ 8 ].
In this paper, we study the art gallery problem when the instance is a poly-
omino, which is the union of connected unit squares (see Fig. 1 a). It is shown
that locating the minimum number of guards with r -visibility in a polyomino

with holes is NP-hard. Here, two points on a polyomino are said to be

r-visible (or ur-seesv ) if the orthogonal bounding rectangle for

u and v

u and v lies

entirely within the polyomino (see Fig. 1 b).
As a corollary of our result, locating the minimum number of guards with -

visibility in an orthogonal polygon with holes is NP-hard. On the other hand, it is

r