The discrete convex combinations problem
by
A. G. Kolpakov
Siberean State University of Telecommunications and Informatics

Let Z_n be a finite set; v_i, i=1, ... , m, v are given vectors. Consider the following convex combinations problem (CCP): indicate all coefficients x_i, i=1, ... , m of convex combinations of the vectors v_i, i=1, ... , m giving the point v . The problem with additional condition: x_i belongs to Z_n is called the discrete CCP.

Using the representation of CCP general solution through the so-called “simplicial” solutions, we develop an algorithm constructing all solution of the discrete CCP. The algorithm constructs a tree, which branches correspond to solutions of the problem. The algorithm was coder for computer.

Date received: October 12, 2000