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?


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))


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)



$\vec v = (0.3689076,0.3689076,0.2621847)$

which is indeed a valid $\vec v$.

  • $\begingroup$ What's tricky here is your usage of $L_\infty$. If you used $L_2$, there'd be an obvious linear programming solution. $\endgroup$ Dec 7, 2019 at 17:16
  • $\begingroup$ @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 :( $\endgroup$ Dec 7, 2019 at 17:17
  • $\begingroup$ 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. $\endgroup$ Dec 7, 2019 at 17:23
  • $\begingroup$ $L_\infty$ is the norm that minimizes the maximum distance. Basically what you are using. $\endgroup$ Dec 7, 2019 at 17:40
  • 1
    $\begingroup$ This is analogous to the smallest-circle problem, except on the unit sphere instead of the plane. $\endgroup$
    – user856
    Dec 7, 2019 at 18:02

1 Answer 1


One idea would be to mimic this planar algorithm on the surface of a unit sphere, where the tips of your vectors lie:

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.


"In this paper we study the problem of constructing a triangulation that minimizes the maximum angle over all triangulations of a finite point set with or without prescribed edges. We call such a triangulation a minmax angle triangulation. Although avoiding small angles is related to avoiding large angles,the Delaunay triangulation does not minimize the maximum angle... [W]e solve the problem by an iterative improvement method based on what we call the edgeinsertion scheme."

  • $\begingroup$ Thank you @Joseph - far above my level of maths :( $\endgroup$ Dec 10, 2019 at 17:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .