No label defined (Q3980665)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 22820
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 22820

      Statements

      26 June 1992
      0 references
      convex hull
      0 references
      permutation
      0 references
      0 references
      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)\).
      0 references

      Identifiers