Download barvinok: User Guide
Transcript
•
×
•
×
•
•
×
•
×
Figure 5.68: The Hilbert basis and the integer hull of a truncated cone
Since the rk are also among the b j , this can be simplified to checking whether there
exists a rational solution for α j to
X
X
bi =
α jb j
with α j ≥ 0 and
α j ≥ 1.
j,i
j,i
Example 5.69 Consider the cone
C = pos {(2, −3), (3, 4)},
shown in Figure 5.68. The Hilbert basis of this cone is
{(0, 0), (2, −3), (3, 4), (1, 1), (1, −1), (1, 0)}.
We have (1, 0) = 12 (1, 1) + 12 (1, −1), while (1, 1) and (1, −1) can not be written as
overconvex combinations of the other bi , 0. The vertices of the integer hull of C \ {0}
are therefore
{(2, −3), (3, 4), (1, 1), (1, −1)}.
96