Visual Cryptography and Contrast Bounds - Visual Cryptography and Secret Image Sharing - page 222

for j = 0;:::;k1. This equation expresses that the stack of j transparencies
always has the same number of white subpixels and replaces (8.1).
Maximize

nk
i

nk
i

n X n X

x (W)
i

x (B)
i

= (8.5)

i=0 i=0

In this form the linear program is simple enough to solve it directly. We
will track this problem in Sections 8.5 and 8.6.
The linear program has been independently deduced by several researchers.
(Variable transformations like x (W)
i

x (W i are common.
This makes the results look quite different in various articles. Always check
the meaning of the variables.)

= i

= x (W)

ni or x (W) i

8.3 Approximate Inclusion Exclusion
The well-known inclusion-exclusion-formula states.
jA 1 [A 2 [:::[A n j = X
i

jA i j X
i<j

jA i \A j j+

X

jA i \A j \A k j::: (1) n jA 1 \:::\A n j :

i<j<k

Obviously, every term on the right-hand side is needed to determine the size
of the union. At this point we can ask whether it is possible to give an ap-
proximate inclusion-exclusion formula. More formally we ask:
Given integers m;n with m n and sets A 1 ;:::;A n and B 1 ;:::;B n where
not all Bi i are empty and where

=

\ \

A i B i

i2S i2S

for every subset S f1;:::;ng such that jSj < m, what is the smallest (or
largest) possible value for the fraction

jA 1 [:::[A n j
jB 1 [:::[B n j ?
The problem of approximate inclusion-exclusion is closely related to con-
trast bounds in visual cryptography schemes. For n-out-of-n and (n1)-out-of-
n scheme the solution of the approximate inclusion-exclusion problem trans-
lates directly to a contrast optimal visual cryptography scheme (see Theo-
rem 4 for the details of the translation). Other applications of the approximate
inclusion-exclusion are constant depth circuits and Boolean functions [15].