Аннотация:
Пусть $\{x_1,\dots,x_n\}$ – конечное множество векторов в $\mathbb R^m$, $x_1+\dots+x_n=0$ и $B=\mathrm{conv}\{x_1,\dots,x_n\}$ – выпуклая оболочка этого множества. Ранее было установлено, что существует такая перестановка $\pi=(\pi_1,\dots,\pi_n)$, что
$$
\sum_{i=1}^{n}x_{\pi_i}\in mB, \quad k=1,\dots,n.
$$
В работе показано, что суммирование векторов возможно внутри тела меньшего бъема: для любого вектора $a\in\mathbb R^m$ строится такая перестановка $\pi=(\pi_1,\dots,\pi_n)$, что
$$
\sum_{i=1}^{n}x_{\pi_i}\in (m-1)B+B_a, \quad k=1,\dots,n,
$$
где $B_a=\mathrm{conv}\{0,a-\frac1mB\}$. Конструктивно находится такой вектор $a\in\mathbb R^m$, что $(m-1)B+B_a\subseteq mB$. Перестановка $\pi$ находится алгоритмом трудоемкости $O(m^2n^2)$.