Volume 17, No 6, 2010, P. 5667
UDC 519.146
A. S. Kozlov
On compact vector summation within minimal strip
Abstract:
This work proposes a new problem of compact vector summation on the plane. Here the summation domain is a closed strip of unfixed direction. The goal is to find the minimal value $\rho$ such that, for an arbitrary finite family of vectors on the plane with the norm of each vector at most 1 and with the total sum equal to zero, there exists a strip of width $\rho$ such that the given vector family can be summed (in some order) within it. Three variants of the problem are considered: strict, nonstrict, and $k$nonstrict. In the strict case, it is forbidden for partial sums to leave the strip. In the nonstrict case, it is forbidden for any two consecutive partial sums to leave the strip. In the case of $k$nonstrict summation, it is forbidden for any $k+1$ consecutive partial sums to leave the strip. For each of the above three cases we obtain nontrivial bounds on the values of the objective function: $1\le\rho\le\frac32$, $\frac12\le\rho_{ns}\le1$, and $\frac1{k+1}\le\rho_k\le\frac12$, where $k\ge2$.
Il. 2, bibliogr. 24.
Keywords: vector summation within strip, compact vector summation, nonstrict vector summation, efficient algorithm.
Kozlov Alexander Sergeevich ^{1}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
email: alexandr_kozlov@ngs.ru
