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

Minimize s + t subject to

A 0 u + (s;:::;s) c (8.19)

A 0 u + (t;:::;t) c () A 0 (t;:::;t) c (8.20)

Equations (8.19) and (8.20) just state that

i=0;:::;n (c i A 0 i u)
t max

s max

i=0;:::;n (A 0 i uc i ):

In the optimal solution these inequalities must be equalities, i.e.,

i=0;:::;n (c i A 0 i u)

s = max (8.21)

i=0;:::;n (A 0 i uc i ):

t = max (8.22)

Now we translate these equations into the language of polynomials. Re-
member that c i = p(i) for a k-th degree polynomial and that the j-th row
of A is the evaluation of a j-th degree polynomial q j . The polynomials q j
(j = 0;:::;k 1) form a basis of the vector space P k1 of all polynomials of
a degree up to k 1.
So we may write the dual problem as:
Determine

= min

q2P k1 i=0;:::;n (p(i) q(i)) +

max

i=0;:::;n (q(i) p(i))

max : (8.23)

By adding the right constant to q, we can choose max i=0;:::;n (p(i)q(i)) =
max i=0;:::;n (q(i) p(i)), which simplies (8.23) to

= min

q2P k1

max
i=0;:::;n

jp(i) q(i)j : (8.24)

The low terms of p lie in P k1 , so the problem is just to approximate the
term of degree k. Since

nk
i

n
i

1

p(i) =

(ni)!
(nik)!

(nk)!
n!

=

(ni)(n 1 i)(n (k 1) i)
n(n 1)(n (k 1))

=

1 i
n

i
n 1

i
n (k 1)

= 1 1

the highest degree term of p(i) is (1) k =n k i k where n k = n(n1)(nk+1).