The name is absent

1 Introduction

Given a polytope P, for example, the convex hull of n ⅛ 1 affinely independent
vectors of Rⁿ, the question is to determine whether P contains an integral point
or not. We develop a simplicial algorithm to solve the problem. The algorithm
is based on a specific integer labeling rule and the well-known ∕<ι-triangulation of
Rⁿ. The main feature of the algorithm can be described as follows: The algorithm
subdivides Rⁿ into п-dimensional simplices such that all integral points of Rⁿ are
vertices of the triangulation, and then assigns an integer to each integral point
of Rⁿ according to the labeling rule. Starting from an arbitrary integral point,
the algorithm generates a sequence of adjacent simplices of varying dimension and
terminates with either the YES or (exclusively) NO answer within a finite number
of steps. In the YES case, the algorithm Ends an integral point in P. The NO
answer shows that there is no integral point in P.

Our work was motivated by the works of Scarf [11] and of Dang and van
Maaren [1]. However, Scarf’s algorithm is based on primitive sets. Although Dang
and van Maaren’s algorithm is also based on simplices, it does not guarantee that the
polytope has no integral point if no integral point can be found by their algorithm.
The algorithm and the labeling rule in this paper are very different from Dang and
van Maaren theirs. We would also like to point out that our algorithm could date
back to the work of van der Laan and Talman [5], although their algorithm was
introduced to compute a fixed point of a continuous function.

The remainder of the paper is summarized next. In Section 2 the labeling
rule and basic theorems are introduced. Section 3 gives a full description of the
algorithm in case the polytope is a full-dimensional simplex in some standard form.
In Section 4 we shall demonstrate how to transform the problem of an arbitrary full-
dimensional simplex into the standard form. In Section 5 we apply the algorithm
to general full-dimensional polytopes. In Section 6 we deal with lower-dimensional

<<   1   2   3   4   5   6   >>

More intriguing information