Information Technology Reference
In-Depth Information
opd-tr (
Octilinear Polygon Decomposition into octilinear Triangles and Rec-
tangles
). After providing some preliminary results, we study the computational
complexity of the opd-tr problem and we show that it is NP-hard. Then, we
prove that opd-tr is in APX by providing an
O
(
n
log
n
)-time 16-approximation
algorithm. We also provide an
)-time 3-approximation algorithm for
opd-tr when the input is restricted to a subclass of octilinear polygons. The
approximation algorithms have been achieved by exploiting results on a strictly
related problem, that is the
Octilinear Polygon Decomposition into octilinear
Convex Components
(opd-c), which also has theoretical interest in itself. We
show that this problem is NP-hard and we provide an
O
(
n
log
n
)-time exact
algorithm for the decomposition of a subclass of octilinear polygons.
Due to lack of space, many proofs are omitted (they will be given in the full
version).
O
(
n
log
n
2 Definitions and Problem Statements
In this paper we consider the following types of polygonal objects:
-a
polygon
is a compact region of the plane, bounded by a simple closed
polygonal line. A polygon may also have
holes
, that is internal pairwise-disjoint
polygonal lines delimiting regions of the plane not belonging to the polygon
itself;
-a
component
is a polygon without holes;
-a
multiple polygon
P
P
is a set of polygons. The intersection of any two elements
of
P
, if non-empty, consists totally of edges and vertices.
The
boundary
of a polygon
P
consists of all points of the polygonal lines
defining
P
and its holes, while the
interior
of
P
consists of all points of
P
that
do not belong to the boundary of
.
A polygonal line can be represented by a finite sequence of vertices
P
v
1
,v
2
,...,v
n
and edges [
v
n
,v
1
] such that two edges share at most
one point and this point is shared only if the edges are consecutive.
Let us consider non-oriented directions in the plane, and define them accord-
ing to the angle they form with respect to the
v
1
,v
2
]
,
[
v
2
,v
3
]
,...,
[
v
n−
1
,v
n
]
,
[
-axis. Directions forming angles
multiples of 90
◦
are called
rectilinear
, while those forming angles multiples of
45
◦
are called
octilinear
. Notice that, there are two rectilinear and four octilinear
directions. A polygon edge parallel to an octilinear (rectilinear, resp.) direction
is called octilinear edge (rectilinear edge, resp.).
x
Definition 1.
An octilinear polygon (rectilinear polygon, resp.) is a polygon
whose edges are all octilinear (rectilinear, resp.).
Figure
1
shows internal angles of octilinear and rectilinear polygons. We call
the angles of 45
◦
,90
◦
, 135
◦
, 225
◦
, 270
◦
, 315
◦
a, b, c, d, e
f
being of type
and
,
respectively (and, we extend the notion of
type
to vertices: the type of
v
i
is the
type of the angle at
v
i
). Without loss of generality, we do not consider polygons
Search WWH ::
Custom Search