The name is absent

polytopes. Concluding remarks are found in Section 7.

2 Integer labeling Rule

The problem in this section is to test the integral property of an n-dimensional
simplex P given by

P = {x E Rⁿ ∖ Ax < b},

where cy^τ = (ад,...,⅛) is the г-th row of the n ⅛ 1 by n matrix A for i = 1, ∙ ∙ ∙,
n + 1, and b = (b₁, ∙ ∙ ∙ , 7,,₊∣ )^τ is a vector of Rⁿ⁺¹. Without loss of generality we
shall assume throughout the paper that α₁, ∙ ∙ ∙, a_n+1 are integral vectors of Rⁿ, and
b = (δ₁, ∙ ∙ ∙ ,δ_ra+1)^τ is an integral vector of Rⁿ⁺¹. Notice that since the simplex P
is full-dimensional, the origin of Rⁿ is contained in the interior of the convex hull
of the vectors α₁, ∙ ∙ ∙, a_n+1. As usual, Zⁿ denotes the set of all integral points in
Rⁿ. Let N denote the set { 1,..., n ⅛ 1 } and N_i the set N without the index г, for
i E N. Now we introduce the following labeling rule.

Labeling Rule: To x E Zⁿ the label /(æ) = i is assigned if i is the smallest index
for which

flʃx — bi = max{ ajx — bj ∖ ajx — bj > 0, j E N }.

If ɑʃx ≤ bi for all i = f,...,n ⅛ 1, then the label /(æ) = 0 is assigned to x.

Notice that if /(æ) = 0, then P contains at least one integral point. Let T
be the K₁ -triangulation of Rⁿ to be described in the next section. This simplicial
subdivision of Rⁿ is such that the collection of the vertices of simplices in T is the
set of all integral points of Rⁿ. We denote a simplex with vertices x¹,...,xⁿ⁺¹ by
σ(≈¹,..., æⁿ⁺¹). Given an п-dimensional simplex σ(≈¹,..., æⁿ⁺¹) in T, let

i(σ) = {∕(_a∙¹),...,⅛ι∙"+¹)}.

<<   1   2   3   4   5   6   7   >>

More intriguing information