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.7900123596191406
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