RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2010 Volume 17, Issue 6, Pages 56–67 (Mi da630)

On compact vector summation within minimal strip

A. S. Kozlov

S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia

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.

UDC: 519.146

Received: 16.06.2010
Revised: 28.08.2010



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024