On compact vector summation within minimal strip

A. S. Kozlov

Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 6, pp. 56-67

Résumé

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.

Détail

Keywords: vector summation within strip, compact vector summation, nonstrict vector summation
Mots-clés : efficient algorithm.