Information Technology Reference
In-Depth Information
1, respectively. Note that, in both cases forbidden vertices have measure greater
than zero.
The
total measure
of an octilinear polygon
P
with vertices
v
1
,v
2
,...,v
n
is
)=
i
µ
P
(
defined as
µ
(
P
v
i
), and the
total measure
of a multiple octilinear
)=
i
µ
polygon
P
i
).
According to the notion of total measure we could say that solving the opd-
tr (or opd-c) problem means to find the smallest sequence of octilinear cuts
that reduces
P
with polygons
P
1
,P
2
,...,P
n
is defined as
µ
(
P
(
) to zero. Hence, we can use the notion of measure to define
which kind of cuts are necessary to solve the opd-tr and opd-c problems. From
now on, by
cut
we always mean a cut [
µ
(
P
v, p
], where
v
is a forbidden vertex and
p
is either a vertex or a point internal to some edge. The previously introduced
concepts of vertex-cuts and point-cuts are extended as follows.
Definition 4.
Terminology about cuts:
v, v
]
,where
-
vertex-cut:
a vertex-cut (shortly, vcut) is a cut
[
v
is a forbidden
v
is any other vertex. There are 5 different versions of vcuts:
vertex and
-
2
represents how much the overall measure of an
octilinear polygon decreases by applying the cut.
A forbidden-vertex-cut (shortly, fvcut) is a cut
[
n
-vcut, where
−
2
≤ n ≤
v, v
]
, where both
v
are
v
and
forbidden.
point-cut:
v, p
v
-
a point-cut (shortly, pcut) is a cut
[
]
,where
is a forbidden
vertex and
p
is a point internal to some edge. There are 2 different versions
of pcuts:
-
b, b
-pcut, if the cut generates at
p
two angles of type
b
;
-
a, c
-pcut, if the cut generates at
p
angles of type
a
and
c
.
Lemma 1.
[
16
]
Solutions to the
opd-tr
−
problem can be found by using
-
2
vcut or
b, b
-pcut only.
Lemma 2.
Solutions to the
opd-tr
problem may require the following cuts:
n
-vcut,
−
1
≤ n ≤
2
,
b, b
-pcut or
a, c
-pcut.
It remains open to check whether
−
2
-vcuts are necessary to solve the opd-tr
problem.
Definition 5.
Octilinear (multiple) polygons having no fvcuts are called
non-
degenerated (multiple) polygons
.
The following lemma provides a useful result which is valid for both the opd-tr
and opd-c problems.
Lemma 3.
Let
be a non-degenerated multiple polygon. If there exists a decom-
position into basic components (convex components, respectively) that requires
µ
P
P
)
cuts, then it is an optimal solution for the
opd-tr
problem (for the
opd-c
problem, respectively).
(
Search WWH ::
Custom Search