Information Technology Reference
In-Depth Information
- for the rectilinear case, the presence of vertex-cuts represents a noteworthy
situation, since they belong to the solution. In the octilinear case this is not
true, as shown by Fig.
2
b
, where the vertex-cut [
v
1
,v
2
] does not belong to any
minimal solution.
v
2
v
1
(
a
)
(
b
)
Fig. 2.
Examples of decomposition of an octilinear polygon. The vertex-cut [
v
1
,v
2
]
does not belong to the solution of the opd-tr problem.
3.1 Cuts for the OPD-TR Problem
Concerning the opd-tr problem, note that a polygon is a basic component if
and only if its internal angles are of type
. This implies that, solving
the opd-tr problem requires to use octilinear cuts that remove vertices of type
c
a
and
b
. Similarly, for the opd-c problem, octilinear cuts must remove
vertices of type
,
d
,
e
and
f
. All the vertices to be removed can be considered as
“forbidden” in the corresponding problem.
d
,
e
and
f
Definition 2.
Vertices (or angles) of type
c
,
d
,
e
and
f
are
forbidden for the
opd-tr problem
. Vertices (or angles) of type
d
,
e
and
f
are
forbidden for the
opd-c problem
.
We simply use the term
forbidden
when the problem is clear or when we have
properties that hold for forbidden vertices/angles independently from the prob-
lemathand.
Definition 3.
Let
v
a vertex of an octilinear polygon
P
. The measure of
v
in
P
corresponds to the minimum number of octilinear cuts required to divide the
internal angle in
into subangles of type non-forbidden or
180
◦
. The measure
v
of
v
in
P
is denoted by
µ
P
(
v
)
.
Concerning the opd-tr problem, by definition, the measure of vertices of type
a
are 0, 0, 1, 1, 1, and 2, respectively. Concerning the opd-c
problem, the measure of vertices of type
,
b
,
c
,
d
,
e
,and
f
a
,
b
,
c
,
d
,
e
,and
f
are0,0,0,1,1,and
Search WWH ::
Custom Search