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 Rn ∖ Ax < b},
where cyτ = (ад,...,⅛) is the г-th row of the n ⅛ 1 by n matrix A for i = 1, ∙ ∙ ∙,
n + 1, and b = (b1, ∙ ∙ ∙ , 7,,+∣ )τ is a vector of Rn+1. Without loss of generality we
shall assume throughout the paper that α1, ∙ ∙ ∙, an+1 are integral vectors of Rn, and
b = (δ1, ∙ ∙ ∙ ,δra+1)τ is an integral vector of Rn+1. Notice that since the simplex P
is full-dimensional, the origin of Rn is contained in the interior of the convex hull
of the vectors α1, ∙ ∙ ∙, an+1. As usual, Zn denotes the set of all integral points in
Rn. 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 Zn 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 K1 -triangulation of Rn to be described in the next section. This simplicial
subdivision of Rn is such that the collection of the vertices of simplices in T is the
set of all integral points of Rn. We denote a simplex with vertices x1,...,xn+1 by
σ(≈1,..., æn+1). Given an п-dimensional simplex σ(≈1,..., æn+1) in T, let
i(σ) = {∕(a∙1),...,⅛ι∙"+1)}.