Balancing unit vectors

DOI10.1006/JCTA.1999.3011MaRDI QIDQ5918028zbMATH OpenOpenAlexFDO

Authors Konrad J. Swanepoel

Publication date 16 April 2001

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0803.0460

zbMATH Keywords

balancing gameFermat-Torricelli pointlocation scienceMinkowski planenormed planevector balancingzonogon

Mathematics Subject Classification ID

Elementary problems in Euclidean geometries (51M04) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21)

Abstract: Theorem A. Let $x_1,\mathrm{...},x_{2k+1}$ be unit vectors in a normed plane. Then there exist signs $eps{i}_1,\mathrm{...},eps{i}_{2k+1}inpm1$ such that $ormsu{m}_{i=1}^{2k+1}eps{i}_i{x}_{i}leq1$. We use the method of proof of the above theorem to show the following point facility location result, generalizing Proposition 6.4 of Y. S. Kupitz and H. Martini (1997). Theorem B. Let $p_0,p_1,\mathrm{...},p_n$ be distinct points in a normed plane such that for any $1leqi<jleqn$ the closed angle $angle{p}_i{p}_0{p}_j$ contains a ray opposite some $overrightarrow{p}_0{p}_k,1leqkleqn$. Then $p_0$ is a Fermat-Toricelli point of $p_0,p_1,\mathrm{...},p_n$, i.e. $x=p_0$ minimizes $su{m}_{i=0}^{n}ormx-p_i$. We also prove the following dynamic version of Theorem A. Theorem C. Let $x_1,x_2,\mathrm{...}$ be a sequence of unit vectors in a normed plane. Then there exist signs $eps{i}_1,eps{i}_2,\mathrm{...}inpm1$ such that $ormsu{m}_{i=1}^{2k}eps{i}_i{x}_{i}leq2$ for all $kinN$. Finally we discuss a variation of a two-player balancing game of J. Spencer (1977) related to Theorem C.

Review text

For \(2k+1\) unit vectors \(x_i\) in an arbitrary normed plane \(M^2\) the author confirms the existence of coefficients \(\lambda_1, \dots, \lambda_{2k +1}\in\{-1;1\}\) such that \[ \left\|\sum^{2k+1}_{i=1} \lambda_i x_i\right \|\leq 1, \] and he uses this to prove a result in the spirit of location science: If for distinct points \(p_0,p_1, \dots,p_n\in M^2\) and any \(1\leq i<j\leq n\) the closed angle \(\sphericalangle p_ip_0p_j\) contains a ray opposite to some \(\overset\longrightarrow{p_0p_k}\), then \(x=p_0\) minimizes \[ \sum^n_{i=0}\|x-p_i\|. \] A dynamic version of the first statement is proved, too: For a sequence of unit vectors \(x_1,x_2, \dots\in M^2\) there exist coefficients \(\lambda_1, \lambda_2,\dots \in \{-1;1\}\) such that \[ \left\|\sum^{2k}_{i=1} \lambda_ix_i \right\|\leq 2 \] for all \(k\in N\). As shown, these results are strongly related to a two-player game which is due to J. Spencer (1977).

Recommendations

• Balancing vectors in the max norm
• Balanced partitions of vector sequences
• Vector balancing games with aging
• A balancing strategy

Cites work

• Balancing game with a buffer
• Balancing games
• Geometrical properties of the Fermat-Weber problem
• scientific article; zbMATH DE number 1054765 (Why is no real title available?)
• scientific article; zbMATH DE number 949298 (Why is no real title available?)
• Lectures on Polytopes
• On some combinatorial questions in finite-dimensional spaces
• Steiner minimal trees

Cited in

(8)

• Selectively balancing unit vectors
• The convexification effect of Minkowski summation
• The Fermat--Torricelli problem in normed planes and spaces
• Helly type theorems for the sum of vectors in a normed plane
• The sign-sequence constant of the plane
• Vector balancing games with aging
• LARGE SIGNED SUBSET SUMS
• Double-jump phase transition for the reverse Littlewood-Offord problem

This page was built for publication: Balancing unit vectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918028)