6
$\begingroup$

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$.

$\endgroup$
  • $\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$ – Don Thousand Dec 7 '19 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$ – user6376297 Dec 7 '19 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$ – user6376297 Dec 7 '19 at 17:23
  • $\begingroup$ $L_\infty$ is the norm that minimizes the maximum distance. Basically what you are using. $\endgroup$ – Don Thousand Dec 7 '19 at 17:40
  • 1
    $\begingroup$ This is analogous to the smallest-circle problem, except on the unit sphere instead of the plane. $\endgroup$ – Rahul Dec 7 '19 at 18:02
1
$\begingroup$

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."

$\endgroup$
  • $\begingroup$ Thank you @Joseph - far above my level of maths :( $\endgroup$ – user6376297 Dec 10 '19 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.