
The Power of Polyhedra 47
Rays
Lines
Inequalities
Equalities
Rays
Lines
Inequalities
Equalities
Polyhedron C
Transformed
Constraints
T
T
Sat
Dual
Polyhedron A
Rays
Compute
Dual
Reduce
Constraints
Figure 2.8 Computation of preimage.
2.4.9 Preimage
Preimage is the inverse operation of image. That is, given a domain D
defined
as
D
= {x
|A
x
≥ 0,x
= R
,A
R
≥ 0, ≥ 0}
and a transformation T , find the domain D which when transformed by T
gives D
. The relation x
= Tx still holds. (Refer again to Figure 2.6.) The
result D is
D = {x |A
Tx ≥ 0,x= R,A
TR ≥ 0, ≥ 0}
= {x |Ax ≥ 0,x= R,AR ≥ 0, ≥ 0}
In the result, A = A
T and R = dual(A). This procedure is illustrated in
Figure 2.8. ...