Information Technology Reference
In-Depth Information
2 Definitions and Results
The definitions of polyominoes and visibility are mostly from [ 2 , 14 ]. A poly-
omino P is a plane geometric figure formed by joining one or more identical
squares edge to edge. A polyomino is a special case of a polyform, which is a
plane figure constructed by joining together identical basic polygons. We refer to
the unit squares as cel ls . Figure 1 (a) is an example of a polyomino
P
of 16 cells
with a hole of two cells.
Two points
v
and
u
in
P
are said to be r-visible (or vr-seesu ) if the orthogo-
nal bounding rectangle for
lies entirely within the polyomino (see Fig. 1 ).
Here, the rectangle may contain points on the boundary of
v
and
u
, but the rectan-
gle must not contain any hole of the polyomino. (The term rectangle is used to
denote the union of the boundary and of the interior.)
It is often useful to extend the notion of visibility to other geometric objects
besides points. We say that two geometric objects
P
X
and
Y
are
r
-visible if and
only if for all points
x ∈ X
and
y ∈ Y
we have that
xr
-sees
y
. For example, a
cell
of a polyomino is said to be r-visible from a point y if every point on and
inside the boundary of
X
X
is
r
-visible from
y
.
u
(a)
(b)
v
w
(c)
(d)
Fig. 3. Thenumberof r -visible cells depends on the position of the point in a cell.
(a) A polyomino P of 16 cells. (b) 11 cells are r -visible from point u . (c) 14 cells are
r -visible from point v . (d) 13 cells are r -visible from point w .
-visible
from at least one of the points. In general, the number of coverable cells from a
point depends on the position of the point in the cell (see Fig. 3 ). However, the
polyomino constructed in Sect. 3 does not depend on such positions. In other
A set of points is said to cover a set of cells if each of the cells is
r
Search WWH ::




Custom Search