scientific article; zbMATH DE number 22820

From MaRDI portal
Publication:3980665





Let \(\{x_ 1,\dots,x_ n\}\) be a finite set of vectors in \(R^ n\), \(x_ 1+x_ 2+\dots+x_ n=0\) and \(B=\text{conv}\{x_ 1,\dots,x_ n\}\) the convex hull of this set. Formerly it was proved (the author does not cite the paper) that there is a permutation \(\pi=(\pi_ 1,\dots,\pi_ n)\) such that \(\sum_{i=1}^ k x_{\pi_ i}\in mB\) (\(k=1,\dots,n\)). In this paper it is shown that the summation of vectors is possible inside a solid of smaller volume: for any vector \(a\in R^ m\) a permutation \(\pi=(\pi_ 1,\dots,\pi_ n)\) is found such that \(\sum_{i=1}^ k x_{\pi_ i}\in(m-1)B+B_ a\) (\(k=1,\dots,n\)), where \(B_ a=\text{conv}\{0,a-{1\over m}B\}\). Constructively we find a vector \(a\in R^ n\) such that \((m-1)B+B_ a\subseteq mB\). The permutation \(\pi\) is obtained by an algorithm of order \(O(m^ 2n^ 2)\).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3980665)