# how to find a vector forming the smallest possible angle with a set of other vectors

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$$. • What's tricky here is your usage of$L_\infty$. If you used$L_2$, there'd be an obvious linear programming solution. – Don Thousand Dec 7 '19 at 17:16 • @Don thank you for your comment, but unfortunately I don't know what you mean. If I have implied that I want to use$L_{\infty}$, it was not intentional (I don't know what that is). Sorry :( – user6376297 Dec 7 '19 at 17:17 • Perhaps however I understand what you mean by 'obvious linear programming solution', because in fact I don't need the norm of$\vec r$, which is the same for all dot products; then$\vec r = (x,y,z)$could be the unknown vector of the LP task, and I would need to maximize$D$such that all$\vec r \cdot \vec v_i \ge D$. At least, I guess so. – user6376297 Dec 7 '19 at 17:23 •$L_\infty\$ is the norm that minimizes the maximum distance. Basically what you are using. – Don Thousand Dec 7 '19 at 17:40
• This is analogous to the smallest-circle problem, except on the unit sphere instead of the plane. – user856 Dec 7 '19 at 18:02

Edelsbrunner, Herbert, Tiow Seng Tan, and Roman Waupotitsch. "An $$O(n^2 \log n)$$ Time Algorithm for the Minmax Angle Triangulation." SIAM Journal on Scientific and Statistical Computing 13, no. 4 (1992): 994-1008. PDF download.