Not sure if this has been asked before - I searched for it and could not find anything resembling what I need, so I'd appreciate if anyone could please help or point me to relevant posts/literature.
[And BTW, apologies for possibly not using the correct mathematical notation].
I have a set of $k$ vectors of length $1$, which I obtain by subtracting a reference point $P$ from $k$ other points $B_1, B_2, ..., B_k$, and then dividing each by its norm.
If the points are expressed as ordered sets of coordinates, then:
$$\vec v_i = \frac {B_i - P} {||B_i - P||} $$
All $B_i$'s are distinct, and none of them coincides with $P$.
Here are 4 example vectors:
$\vec v_1 = (-\frac 1 5, \frac 9 {10}, \frac {\sqrt 3} {2 \sqrt 5})$
$\vec v_2 = (\frac 3 5, \frac 2 {5}, 2 \frac {\sqrt 3} {5})$
$\vec v_3 = (\frac 9 {10}, - \frac 1 {5}, \frac {\sqrt 3} {2 \sqrt 5})$
$\vec v_4 = (\frac 3 {10}, \frac 9 {10}, - \frac {1} {\sqrt 2 \sqrt 5})$
Question: how to find a vector $\vec r$ such that the largest of the $k$ angles between $\vec r$ and each $\vec v_i$ is minimized (all angles being $\le \pi$), i.e. such that the smallest of the $k$ dot products between $\vec r$ and each $\vec v_i$ is maximized?
If I had only $\vec v_1$ and $\vec v_2$, $\vec r$ would be $\vec v_1 + \vec v_2$, as then:
$\frac {\vec r \cdot \vec v_1} {||\vec r||} = \frac {\vec r \cdot \vec v_2} {||\vec r||} \approx 0.868$
Taking $\vec r$ any 'closer' to $\vec v_1$ would make the angle with $\vec v_2$ larger (i.e. the dot product smaller).
However, when I have more than 2 vectors, I don't know how to do the calculation.
I tried numerically, and I found that, for instance, when I have $\vec v_1, \vec v_2, \vec v_3$, only $\vec v_1$ and $\vec v_3$ 'matter', so $\vec r = \vec v_1 + \vec v_3$.
$\vec v_1,\vec v_3$ happens to be the pair of vectors with the smallest dot product ($\approx - 0.21$).
Seeing this, I thought that only the pair $\vec v_i, \vec v_j$ with the largest angle to start with mattered, and when the vectors are in 2D (i.e. when I don't use the 3rd coordinate) this actually works: I just need to loop over all the possible $\frac {k (k-1)} 2$ pairs of vectors, find the pair that has the smallest dot product, and $\vec r$ is the sum of those two vectors.
However, this does not work in 3D.
Even in 3D, and including $\vec v_4$ in the set, $\vec v_1,\vec v_3$ is still the pair of vectors with smallest dot product.
However the numerical result is $\vec r \approx (0.632, 0.632, 0.449)$, which gives the same dot product ($\approx 0.616$) with $\vec v_1$, $\vec v_3$ and $\vec v_4$.
I suppose this cannot be a coincidence, and it makes me suspect that $\vec r$ is always some type of combination of the $\vec v_i$'s, but I would not know how to derive a formula or method, or in fact if it makes sense at all.
The fact that I minimize the maximal angle is reminiscent of linear programming, but then again I have no clue if and how this could be applied here, given that the dot product is not linear.
And in fact ultimately my goal would be to have a method that works with vectors in any number of dimensions.
Any ideas/suggestions?
Thanks!
EDIT after some further work
Suppose I know that I want to find the vector that has the same angle with 3 other vectors, in this case the ones found via the numerical procedure.
$\vec r =(x,y,z)$
$\vec r \cdot \vec v_1 = a$
$\vec r \cdot \vec v_3 = a$
$\vec r \cdot \vec v_4 = a$
If I solve this system, I get:
$[x=1.0254 \cdot a, y=1.0254 \cdot a, z=0.7287 \cdot a]$
Any $a > 0$ gives me a valid $\vec r$.
But then I still don't know how to identify the 3 vectors in a general case, or actually if this is indeed a generally valid method.
If it is, I would guess that in $d$ dimensions I need to use $d$ vectors(?).
Maybe I should investigate the LP solution Don hinted to in the comment below...
EDIT 2 attempt to use linear programming
It seems to work, at least for this example. The R code below:
v1 <- c(-1/5,9/10,sqrt(3)/2/sqrt(5))
v2 <- c(3/5,2/5,2*sqrt(3)/5)
v3 <- c(9/10,-1/5,sqrt(3)/2/sqrt(5))
v4 <- c(3/10,9/10,-1/sqrt(2)/sqrt(5))
require(Rsymphony)
obj = c(1,rep(0,3))
mat = cbind(-1,rbind(v1,v2,v3,v4))
mat = rbind(mat,c(0,rep(1,3)),c(0,rep(1,3)))
dir = c(rep(">=",4),"<=",">=")
rhs = c(rep(0,4),1,-1)
sol <- Rsymphony_solve_LP(obj,mat,dir,rhs,max=TRUE)
print(sol$solution[2:4])
returns:
$\vec v = (0.3689076,0.3689076,0.2621847)$
which is indeed a valid $\vec v$.
