1

I'm curious if there's an algorithmic way to find the minimal vector sum of $N$ vector magnitudes by applying a rotation $\Phi$ to each individual vector. As an example in two dimensions, if I have three vector magnitudes $||x||, ||y||, ||z||$ that obey the triangle inequality, I can find the appropriate angles to force the vector sum to zero. If they don't, I can still find some unique, global minima.

For four equal magnitude vectors, there's a global minima but it's not unique, as I can apply four rotations of $\Phi = \pm \pi/2$ to create a cube.

I'm hoping there's an algorithmic way to solve this for $N$ vector magnitudes, specifically for two-dimensional vectors.

Brady S
  • 13

1 Answers1

0

Alright Brady, here's my stab at it. ;)

First of all, any solution where sum $= 0$ can be made into a triangle (I'll prove this later), and so this amounts to the problem: given $n$ positive numbers, partition them so that they satisfy the triangle inequality (where the triangle may have zero area). This can be done as follows:

Take the largest number, call it $b$. Sum the rest and call it $a$. If $a < b$, they cannot form a triangle and the optimal solution is $b - a$. Otherwise, remove a number $a_i$ from $a$. If $a-a_i\leq b+a_i$, then $(a-a_i,a_i,b)$ form a triangle. Otherwise, keep removing numbers from $a$ and adding them to $b$ until this occurs.

Incidentally, this proves the assertion above that any (sum $=0$) solution can be made into a triangle. The only way the algorithm fails to reach 0 (i.e. make a triangle) is if $a<b$, and clearly in this case $b-a$ laid out in a line is the optimal solution for the vector problem.

fferen
  • 116