for i = 1,..., n. Hence
n
ɪɪ) K3x3 ≤ bt
J = I
for i = l,...,n. In summary, we have Ax <b. □
Now we introduce the K1 -triangulation of Rn (see [4, 14, 15]) which underlies
the algorithm. We define a set of n ⅛ 1 vectors of Rn by
q(z) = -e(z),z = 1, ...,n
and
n
q(n + 1) = ∑2e(zλ
i=l
where e(z) denotes the г-th unit vector of Rn^ i = 1,..., n. For a given integer t,
0 ≤ t ≤ n, a Ndimensional simplex or Nsimplex, denoted by σ, is defined as the
convex hull of t ⅛ 1 affinely independent vectors x1, ∙ ∙ ∙, xt+1 of Zn. We usually
write σ = σ(x1, ∙ ∙ ∙ , æi+1) and call x1, ■ ■ -, xt+1 the vertices of σ. A {t — l)-simplex
being the convex hull of t vertices of σ(x1, ∙ ∙ ∙ , æi+1) is said to be a facet of σ.
If x1 E Zn and π = (π(l), ∙ ∙ ∙ , τr(n)) is a permutation of the elements of the set
{ 1, 2,..., n }, then denote by σ(x1, π) the n-simplex with vertices æ1,..., xn+1 where
xt+1 = xt ⅛ e(τr(z)) for each i = l,...,n. The K1 -triangulation of Rn is the collection
of all such simp lices.
Let V be an integral point of Rn. The point v will be the starting point of the
algorithm. Dehne for T being a proper subset of N the regions A(T) by
A(T) = {æ ∈ Rn ∖x = v + ∑Λj<7)A- ≥ O, j ET}.
K'
Notice that the dimension of A(T) equals t with t = ∣T∣. The K1 -triangulation
subdivides any set A(T) into Nsimplices σ(x1 ,π(T)) with vertices æ1, ■■■, xt+1,
where x1 is a vertex in A(T) , 7r(T) = (ττ(l), ∙ ∙ ∙ , π(t)) is a permutation of the
elements of the set T, and xt+1 = xt ⅛ q(tγ(z)), i = 1, ∙ ∙ ∙, t. For a proper subset T
of N a (t — l)-simplex σ(x1,..., xt), 1 < t < n, is called Т-complete if the t vertices