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

words, even if guards are placed on boundaries of cells of Fig. 8 , the number of
coverable cells does not change.
The definitions of a polygon and a polygon with holes are mostly from [ 10 , 12 ].
A polygon is defined by a finite set of segments such that every segment extreme
is shared by exactly two edges and no subset of edges has the same property.
The segments are the edges and their endpoints are the vertices of the polygon.
If each edge of a polygon is perpendicular to one of the coordinate axes, then
the polygon is called orthogonal or rectilinear . If no non-consecutive pair of edges
overlap, then the polygon is said to be simple .
A polygon with holes is a polygon

P enclosing several other polygons H 1 ,

H 2 ,...,H h , the holes. None of the boundaries of P , H 1 ,H 2 ,...,H h may inter-

sect, and each of the holes is empty. P is said to bound a multiply-connected

region with h holes: the region of the plane interior to or on the boundary of P ,

but exterior to or on the boundary of H 1 ,H 2 ,...,H h . Similarly, we define an

orthogonal polygon with holes to be an orthogonal polygon with orthogonal holes,
with all edges aligned with the same pair of orthogonal axes.
An instance of the r-visibility guard set problem for polyominoes is a pair

( P, k ), where P is a polyomino and k is a positive integer. The problem asks

whether there exists a set of . The same

problem for orthogonal polygons with holes can be defined analogously.
Now we are ready to present our main results.

k points in P which covers all cells of P

Theorem 1. The r -visibility guard set problem for polyominoes is NP-hard.

The proof of Theorem 1 is given in the next section. If the whole polyomino
constructed in Sect. 3 (see Fig. 8 ) is regarded as an orthogonal polygon with
holes, then one can see that the proof of Theorem 1 holds also for the following
corollary.

Corollary 1. The r -visibility guard set problem for orthogonal polygons with

holes is NP-hard.

3 NP-hardness of the r -visibility Guard Set Problem

In this section, we will prove Theorem 1 . We construct a polynomial-time trans-
formation from an instance C of PLANAR 3SAT to a polyomino P and an

integer k such that C is satisfiable if and only if there exists a set of k points

in P covering all cells of P .

3.1 PLANAR 3SAT

The definition of PLANAR 3SAT is mostly from [LO1] on page 259 of [ 6 ]. Let
U

be a set of Boolean variables . Boolean varia b les take on
values 0 (false) and 1 (true). If

= {x 1 ,x 2 ,...,x n }

x is a variable in U , then x and x are literals

over U . The value of x is 1 (true) if an d only if x is 0 (false). A clause over U

U {x 1 ,x 3 ,x 4 }

is a set of literals over , such as . It represents the disjunction of