Broadcasting a Means to Disseminate Public Data in a Wireless Environment—Issues and Solutions - Advances in Computers - page 69

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 .