The name is absent

for i = 1,..., n. Hence
n
ɪɪ) K₃x₃ ≤ b_t
J = I

for i = l,...,n. In summary, we have Ax <b.                                  □

Now we introduce the K₁ -triangulation of Rⁿ (see [4, 14, 15]) which underlies
the algorithm. We define a set of n ⅛ 1 vectors of Rⁿ by

_q(_z) = -e(z),z = 1, ...,n

and
n
q(n + 1) = ∑2^e(^zλ
i=l

where e(z) denotes the г-th unit vector of Rⁿ^ 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 x¹, ∙ ∙ ∙, x^t+1 of Zⁿ. We usually
write σ = σ(x¹, ∙ ∙ ∙ , æⁱ⁺¹) and call x¹, ■ ■ -, x^t+1 the vertices of σ. A {t — l)-simplex
being the convex hull of t vertices of σ(x¹, ∙ ∙ ∙ , æⁱ⁺¹) is said to be a facet of σ.
If x¹ E Zⁿ and π = (π(l), ∙ ∙ ∙ , τr(n)) is a permutation of the elements of the set
{ 1, 2,..., n }, then denote by σ(x¹, π) the n-simplex with vertices æ¹,..., xⁿ⁺¹ where
x^t+1 = x^t ⅛ e(τr(z)) for each i = l,...,n. The K₁ -triangulation of Rⁿ is the collection
of all such simp lices.

Let V be an integral point of Rⁿ. 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) = {_æ ∈ Rⁿ ∖_x = _{v +} ∑Λ_j<₇)A- ≥ O, j ET}.

K'

Notice that the dimension of A(T) equals t with t = ∣T∣. The K₁ -triangulation
subdivides any set A(T) into Nsimplices σ(x¹ ,π(T)) with vertices æ¹, ■■■, x^t+1,
where x¹ is a vertex in A(T) , 7r(T) = (ττ(l), ∙ ∙ ∙ , π(t)) is a permutation of the
elements of the set T, and x^t+1 = x^t ⅛ q(tγ(z)), i = 1, ∙ ∙ ∙, t. For a proper subset T
of N a (t — l)-simplex σ(x¹,..., x^t), 1 < t < n, is called Т-complete if the t vertices

<<   5   6   7   8   9   10   11   >>

More intriguing information