Information Technology Reference
In-Depth Information
F
IG
. 38. cut, MAX_cut and MAX_total.
F
IG
. 39. Free cells, restrictive cells, overlapped empty blocks, and obstacles.
Definition 7
( Dense columns) .
A column that is neither
Empty
nor
Sparse
is
Dense
.
With respect to a user request, the minimum required number of passes depends on
dense columns.
R
j
is defined to be the set of rows we need to scan in column
j
based on objects
in columns
j
through
j +
OPR
−
1. This naturally leads to the definition of the cut
at column
j
.
Definition 8.
Let
R
j
={i |∃j
′
,j
j
′
j +
OPR
−
1, such that
C
ij
′
∈ S}
.
Consequently, the
cut
at column
j
is
|R
j
|
.
Definition 9.
The
maximum cut
,
MAX_cut,
is
max
{
cut
j
|
1
j
N }
.
Definition 10.
The
total requested channels
,
MAX_total
,is
|{i | j
such that
C
i,j
∈
S}|
.
We can conclude that
MAX_cut
minimum number of passes
MAX_total
.