Information Technology Reference
In-Depth Information
1.
x
is a point
p
interior to some edge
e
of
P
. Hence the cut [
v, x
] is either a
b, b
are convex and
then they do not need further cuts. So, one cut is sucient to “remove” the
concave vertex
-pcut or a
a, c
-pcut. In both cases, the new angles at
p
v
from
P
.
v
is not forbidden. Also in this case no
further cuts are needed to “remove” the concave vertex
v
of
2.
x
coincides with a vertex
P
, but
v
from
P
.
This proves that the above approach uses
) octilinear cuts exactly. Concern-
ing the execution time, the algorithm performs
µ
(
P
O
(
n
) cuts and each cut can be
performed in
)-time by using the ray-shooting algorithm given in [
1
]. It is
worth to note that, if we need to test whether the input polygon is indeed a non-
degenerated component, then this task can be easily accomplished in
O
(log
n
O
(
n
log
n
)-
time by using a brute-force approach: test whether for each forbidden vertex
v
and for each ray
r
(shoot from
v
along an octilinear direction
d
), the first point
reached by
r
is a forbidden vertex or not.
In [
16
] it has been shown that given a multiple rectilinear polygon
P
consisting
B
P
− E
P
of
k
polygons and
w
holes, then
=4
k −
4
w
. A generalization of this
result is given by the following lemma.
Lemma 5.
Given a multiple octilinear polygon
P
consisting of
k
polygons and
A
P
+2
B
P
+
C
P
− D
P
−
E
P
−
F
P
=8
w
holes, then
3
2
3
k −
8
w
.
Since a convex component
P
has internal angles of type
a
,
b
,
c
only, then, by
P
= 8. As consequence, the number of convex
components which differ by the (circular) sequence of convex angles is finite.
P
+2
P
+
Lemma
5
,wehave3
A
B
C
6 Approximation Results
We start by providing an approximation result for the opd-tr problem restricted
to non-degenerated components. To this end we need the notion of
nice-cut
:
Definition 6.
A cut in an octilinear polygon is called
nice-cut
ifeitheritisa
b, b
-pcut, or it is a
-vcut.
+2
P
Lemma 6.
Let
be a convex component with at least 5 vertices. Then, there
P
exists a nice-cut in
.
Algorithm
1
provides an approximation for the opd-tr problem restricted to
non-degenerated components. This algorithm takes as input a non-degenerated
component
(i.e., an octilinear polygon without holes and without forbidden-
vertex-cuts) and performs, as a preliminary phase, the decomposition of
P
P
into
octilinear convex components. For this preliminary phase, the optimal decom-
position algorithm presented in the proof of Theorem
3
is used. The following
lemmas and remarks are useful to state the approximation bound of Algorithm
1
.
Lemma 7.
Let
P
=
{v
1
,v
2
,...,v
n
}
be a non-degenerated component. Then,
P
µ
P
C
P
+
D
P
+
E
P
+2
F
P
each solution for
requires at least
(
)=
cuts.
Search WWH ::
Custom Search