Decomposing Octilinear Polygons into Triangles and Rectangles - Discrete and Computational Geometry and Graphs - page 25

)= i µ P ( Proof. By definition, v i ) is the minimum number

of octilinear cuts required to divide the internal angle in

µ ( P v i ), where µ P (

v i into non-forbidden

subangles. Hence, each forbidden vertex v i contribute to µ ( P ) by adding 1 or

2. This implies that decomposing P by using less than µ ( P ) cuts requires the

existence of -vcuts, i.e. cuts connecting pairs of forbidden vertices. This is not

the case, since the input multiple polygon

2

P is non-degenerated.

a µ P

Notice that the polygon shown in Fig. 2 ) = 1 cuts. We

close the section by observing that all the four octilinear directions may be
necessary to get the optimal solution to the opd-tr problem.

needs more than (

Lemma 4. Concerning the opd-tr problem, the following properties hold:
1. an optimal solution may require cuts parallel to all the four octilinear direc-
tions;
2. without using all the four octilinear directions may lead to solutions that are
k k

times the optimal one, with arbitrarily large.

4 Complexity of the Main Problem

The computational complexity of the opd-tr problem is stated in Theorem 1 .
For the sake of space, we omit the long proof of this theorem which is borrowed
from [ 12 ], where the problem of decomposing a polygon into a minimum number
of convex components by cuts in the directions of

is a family of non-
oriented directions in the plane) is studied. There, authors have shown that the
problem is NP-hard if

F ( F

|F| ≥ 3 and is solvable in polynomial time if |F| ≤ 2.

Theorem 1. The opd-tr problem is NP-hard.

5 Decomposition into Convex Components

In this section we study the opd-c problem: we start by stating the computa-
tional complexity, and then we provide an optimal algorithm when the input is
restricted to non-degenerated octilinear polygons. This algorithm will be used
to achieve approximation results shown in the next section. We conclude this
section by providing a lemma for multiple octilinear polygons that extends a
property found for rectilinear polygons.

Theorem 2. The opd-c problem is NP-hard.

Theorem 3. There exists an ) -time algorithm for solving the opd-c

problem restricted to non-degenerated octilinear polygons.

O ( n log n

Proof. Given a non-degenerated octilinear polygon , according to Lemma 3 ,we

prove the theorem by showing that there exists a solution for the opd-c problem
that requires

P

µ ( P ) octilinear cuts. We decompose P according to the following

approach: for each concave vertex v , perform a cut [ v, x ] that prolongs an edge

incident to . To show that such an approach produces a solution for the opd-c

problem, consider two different cases, according to

v

x

: