Information Technology Reference
In-Depth Information
Proof. Let us assume that a multiple octilinear polygon
P
consisting of
k
poly-
gons and
holes is given as input to Algorithm 1 . According to Remarks 1 and 2
we have to show that
5
w
F P +3
E P +3
D P +2
C P +
k − w
k − w
16
.
(
C P +
D P +
E P +2
F P )
/
2+
By using the bound
w ≤
(
F
+
E
+
D
)
/
3 on the maximum number of holes we
get:
5 F P +3 E P +3 D P +2 C P + k − w
( C P + D P + E P +2 F P ) / 2+ k − w =
10 F P +6 E P +6 D P +4 C P +2 k 2 w
2 F P + E P + D P + C P +2 k − 2 w
10 F P +6 E P +6 D P +4 C P +2 k 2( F P + E P + D P ) / 3
2 F P + E P + D P + C P +2 k − 2( F P + E P + D P ) / 3
=
28 F P +16 E P +16 D P +12 C P +6 k
4 F P + E P + D P +3 C P +6 k
<
(28 F P +16 E P +16 D P +12 C P +6 k )+(36 F P +36 C P +90 k )
4 F P + E P + D P +3 C P +6 k
=16 .
O
n
Concerning the execution time, the algorithm performs
(
) cuts. Each cut
O
n
can be performed in
(log
)-time by using the ray-shooting algorithm given
in [ 1 ].
It is worth to note that Theorem 4 is based on Algorithm 1 , and now this
algorithm performs, as first step, a non-optimal decomposition of
into convex
octilinear components. Unfortunately, Theorem 2 implies that such a convex
decomposition cannot be performed eciently.
P
7 Conclusion and Future Work
In this work we have introduced the opd-tr problem, which consists in find-
ing the minimal decomposition of an octilinear polygon with holes into basic
components (octilinear triangles and rectangles). This problem is relevant in the
context of modern electronic CAD systems, when the Cavity Model is used to
detect the generation and propagation of electromagnetic noise into multi-layer
PCBs. As main results, we have shown that the opd-tr problem is NP-hard
and proposed a constant-factor approximation algorithm.
We are currently implementing under CGAL the obtained 16-approximation
algorithm. The implementation will be tested by using, as input, a large dataset
from a real multi-layer PCB consisting of
100,000 total vertices. 1 The appli-
cation domain (i.e., electronic CAD) and the size of such a dataset reveal that,
1 The PCB consists of 16 layers and its
13,000 polygons (i.e., cavities) have been
Allegro R PCB designer project file. The polygons have
been approximated into octilinear polygons by using the schematization algorithm
proposed in [ 3 ]. Disregarding the polygons having the area below a given threshold,
we get the final dataset of
extracted from a Cadence R
1,000 octilinear polygons with
100,000 total vertices.
 
Search WWH ::




Custom Search