Information Technology Reference
In-Depth Information
Algorithm 1.
Decomposing a non-degenerated component
Data
: a non-degenerated component
P
=
{v
1
,v
2
,...,v
n
}
Result
: a decomposition of
P
into basic components
foreach
vertex v
i
of type d, e and f
do
1
divide the angle at
v
i
by a cut that prolongs an edge incident to
v
i
;
/* according to the proof of Theorem 3, at the end of this step,
P
is optimally decomposed into convex components
2
*/
3
end
4
while
there are convex components with at least 5 vertices
do
5
take a convex component
C
with at least 5 vertices;
foreach
vertex v
i
of type c
do
6
decompose
C
by using a nice-cut [
v
i
,p
];
/* according to Lemma 6, there exists such a cut in
C
7
*/
end
8
end
9
foreach
convex component C with 4 vertices and different from a rectangle
do
10
decompose
C
;
11
end
12
return
the set of all the obtained basic components
13
Remark 1.
Lemma
7
can be rephrased by stating that each solution for a non-
degenerated component
P
+ 1 basic
components. It is possible to extend easily this result to any multiple octilinear
polygon
P
+
P
+
P
+2
P
requires at least
C
D
E
F
C
P
+
D
P
+
E
P
+
P
with
k
polygons and
w
holes: in such a case, at least (
F
P
)
C
P
+
D
P
+
E
P
+2
F
P
)
2
2
is due to possible forbidden-vertex-cuts (where a cut may connect two forbidden
vertices).
/
2+
k−w
basic components are required. The ratio (
/
Lemma 8.
Let
P
be a non-degenerated component. Algorithm
1
decomposes
P
P
+3
P
+3
P
+5
P
by using at most
2
C
D
E
F
cuts.
Remark 2.
Lemma
8
can be rephrased by stating that Algorithm
1
decomposes
P
P
+1 basic components. This result
can be extended to any multiple octilinear polygon
P
+3
P
+3
P
+5
by producing at most 2
C
D
E
F
P
with
k
polygons and
w
C
P
+3
D
P
+3
E
P
+5
F
P
+
holes: in such a case Algorithm
1
produces at most 2
k−w
basic components.
Theorem 4.
There exists an
)
-time
3
-approximation algorithm for the
opd-tr
problem when the input is restricted to non-degenerated components.
O
(
n
log
n
According to Remarks
1
and
2
, we know that Algorithm
1
is able to process
not only non-degenerated components but also generic multiple octilinear poly-
gons. This implies that we can provide an approximation result for the opd-tr
problem, as follows.
Theorem 5.
There exists an
O
(
n
log
n
)
-time
16
-approximation algorithm for
the
opd-tr
problem.
Search WWH ::
Custom Search