5
$\begingroup$

This is an optimization problem and I am wondering if there's any intuitive (geometric) way to understand the solution of the problem. More complex analytical solutions are also appreciated.

In a 3D sphere, let's start from an initial point located at coordinates $(1, 0, 0)$, where each element corresponds to the $(x, y, z)$ coordinates in the plane. Our only allowed actions are rotating the point around either the $X + Z$ or $-X + Z$ axis (the axis of rotations would be $(X+Z)/\sqrt{2}$ and $(-X + Z)/\sqrt{2}$ respectively. They are vector addition of $X$ and $Z$ and $-X$ and $Z$). The total rotation amount (i.e. the total angle of rotation) must be equal to $\theta ~ (< \pi)$.

What is the optimal strategy in order to minimize the Euclidean distance between the final point and the initial point?

Upon numerical investigation, it appears that rotating by an angle of $\theta/2$ around the $X + Z$ axis, followed by an additional rotation of $\theta/2$ around the $-X + Z$ axis, gives the optimal solution for this problem. An example of this solution is depicted in the figure below.

If this is indeed an optimal solution, why would it be? What is a good way to understand this solution in terms of the geometry of the problem, or any other tools?

Figure

$\endgroup$
7
  • $\begingroup$ Did you want to minimize the distance or maximize it? $\endgroup$
    – David K
    Commented Oct 3, 2023 at 1:35
  • $\begingroup$ @DavidK minimize it $\endgroup$
    – Mohan
    Commented Oct 3, 2023 at 5:36
  • $\begingroup$ Suppose $\theta=1.998\pi$. A single rotation by $\theta$ around either axis will bring you almost back to the starting point. Two rotations of $0.999\pi$ each will take you almost to the farthest point on the sphere. It seems to me you are maximizing distance whether you intended to or not. $\endgroup$
    – David K
    Commented Oct 3, 2023 at 12:59
  • $\begingroup$ Oh, you're absolutely right. I believe that I was thinking about the case of $\theta < \pi$, not $2\pi$. I edited my question. $\endgroup$
    – Mohan
    Commented Oct 3, 2023 at 16:03
  • $\begingroup$ @Cesareo Could you elaborate more? $\endgroup$
    – Mohan
    Commented Oct 3, 2023 at 17:22

2 Answers 2

0
$\begingroup$

To simplify the computations, let's make a transformation of the coordinate system, such that the new coordinate system has its $x'$ axis along the (world coordinates) vector $u_{x'} = \dfrac{1}{\sqrt{2}}(1, 0, 1) $ and the $z'$ axis along $u_{z'} = \dfrac{1}{\sqrt{2}}(-1, 0, 1) $, then the unit vector vector along the $y'$ axis will be

$ u_{y'} = u_{z'} \times u_{x'} = (0, 1, 0) $

So now the new coordinate system can be summarized in relation to the old world coordinate system by

$ p = R_0 p' $

where $p$ is the world coordinates of a point $p$, and $p'$ is its representation in the new coordinate system $Ox'y'z'$

And

$ R_0 = \dfrac{1}{\sqrt{2}} \begin{bmatrix} 1 && 0 && -1 \\ 0 && \sqrt{2} && 0 \\ 1 && 0 && 1 \end{bmatrix} $

The corresponding vector to $p = (1, 0, 0)$ is $p' = R_0^T p = \dfrac{1}{\sqrt{2}}(1,0,-1) $

Now rotating $p$ about $X+Z$ is equivalent to rotating $p'$ about the $x'$ axis, and rotating about $-X + Z$ is equivalent to rotating the corresponding point about the $z'$ axis.

Since rotation about $X+Z$ axis is done first, the total rotation is

$ R = R_{z'} R_{x'} = \begin{bmatrix} c_2 && -s_2 && 0 \\ s_2 && c_2 && 0 \\ 0 && 0 && 1 \end{bmatrix} \begin{bmatrix} 1 && 0 && 0 \\ 0 && c_1 && - s_1 \\ 0 && s_1 && c_1 \end{bmatrix} $

where $c_1 = \cos(\theta_1), s_1 = \sin(\theta_1) , c_2 = \cos(\theta_2) , s_2 =\sin(\theta_2) $

Multiplying out, we get

$ R = \begin{bmatrix} c_2 && - c_1 s_2 && s_1 s_2 \\ s_2 && c_1 c_2 && - s_1 c_2 \\ 0 && s_1 && c_1 \end{bmatrix} $

We have the constraint that $\theta_1 + \theta_2 = \theta \lt \pi $ where $\theta$ is a constant.

This means that if $c = \cos(\theta) , s = \sin(\theta) $ , then

$ c_2 = \cos(\theta_2) = \cos(\theta - \theta_1) = c c_1 + s s_1 $

and

$ s_2 = \sin(\theta_2) = \sin(\theta - \theta_1) = s c_1 - c s_1 $

The final vector after the two rotations is given by

$ f' = R p' $

The two vectors $p'$ and $f'$ have the same length, so the distance between them is minimized when the angle between them is minimized. Assuming $\| p' \| = \| f' \| = 1 $ , then if $\phi$ is the angle between them, then

$ \cos \phi = f'^T p' = p'^T R^T p' $

In this case, our $p' = \dfrac{1}{\sqrt{2} } (1, 0, -1) $, then

$ R^T p' = \dfrac{1}{\sqrt{2} } ( c_2, -c_1 s_2 - s_1, s_1 s_2 - c_1 ) $

And finally we have

$ p'^T R^T p' = \dfrac{1}{2} ( c_2 - s_1 s_2 + c_1 ) $

Using the expressions for $c_2$ and $s_2$, in this expressions, gives us,

$ p'^T R^T p' = \dfrac{1}{2} ( c_1 + c c_1 + s s_1 - s_1 (s c_1 - c s_1) ) $

Writing it out in the normal way, we have

$ p'^T R^T p' = \dfrac{1}{2} ( \cos(\theta_1) (1 + c) + s \ \sin(\theta_1) - s \ \sin(\theta_1) \cos(\theta_1) + c \ \sin(\theta_1)^2 ) $

Now we differentiate this function with respect to $\theta_1$, and equate to zero. This gives

$ -(1 + c) \sin(\theta_1) + s \cos(\theta_1) - s \cos(2 \theta_1) + c \sin(2 \theta_1) = 0 $

This can be simplified to,

$ - \sin(\theta_1) + \sin(\theta - \theta_1) - \sin( \theta - 2 \theta_1) = 0 $

If we let $\theta_1 = \dfrac{\theta}{2} $, then we get a root of the above equation. It remains to verify that it is a maximum (because we want the maximum possible $\cos(\phi)$ ), and for that we take the second derivative,

$D_2 = - \cos(\theta_1) - \cos( \theta - \theta_1) + 2 \cos( \theta - 2 \theta_1) $

Upon plugging $\theta_1 = \dfrac{\theta}{2} $ we get

$ D_2 = - 2 \cos(\theta_1) + 2 = 2 ( 1 - \cos(\theta_1) ) \gt 0 $

Therefore we have a minimum of $\cos(\phi)$ and therefore a maximum of $\phi$, and hence, a maximum of the distance between $p'$ and $f'$.

Further investigation of the roots of the derivative is necessary.

The expression for the derivative is

$ D = - \sin(\theta_1) + \sin(\theta - \theta_1) - \sin( \theta - 2 \theta_1) = 0 $

Combining the first two sinusoids, we get

$ D = 2 \cos \left(\dfrac{\theta}{2} \right) \sin \left( \dfrac{\theta}{2} - \theta_1 \right) - 2 \sin \left( \dfrac{\theta}{2} - \theta_1 \right) \cos \left( \dfrac{\theta}{2} - \theta_1 \right) = 0 $

And this factors as follows,

$ D = 2 \sin \left(\dfrac{\theta}{2} - \theta_1 \right) \left( \cos \left(\dfrac{\theta}{2} \right) - \cos \left(\dfrac{\theta}{2} - \theta_1 \right) \right) = 0 $

And finally, this becomes

$ D = -4 \sin \left(\dfrac{\theta}{2}- \theta_1 \right) \sin \left( \dfrac{\theta}{2} - \dfrac{\theta_1}{2} \right) \sin \left(\dfrac{\theta_1}{2} \right) $

So now we have all the roots as follows:

$\theta_1 = \dfrac{\theta}{2} $

$\theta_1 = \theta $

$ \theta_1 = 0 $

The second derivative is

$D_2 = - \cos(\theta_1) - \cos( \theta - \theta_1) + 2 \cos( \theta - 2 \theta_1) $

At $\theta_1 = \theta $, we have,

$D_2 = - \cos(\theta) - 1 + 2 \cos(\theta) = \cos(\theta) - 1 \lt 0 $

So we have a maximum here.

At $\theta_1 = 0 $ , we have

$D_2 = - 1 - \cos(\theta) + 2 \cos(\theta) = \cos(\theta) - 1 \lt 0 $

So we have two possible local maxima, the function value itself at

$ \theta_1 = \theta $ is

$ \cos \phi = \dfrac{1}{2} ( \cos(\theta_1) (1 + c) + s \ \sin(\theta_1) - s \ \sin(\theta_1) \cos(\theta_1) + c \ \sin(\theta_1)^2 ) $

Evaluating, gives

$ \cos \phi = \dfrac{1}{2} ( c (1 + c) + s^2 - s^2 c + c s^2 ) = \dfrac{1}{2} ( 1 + c) $

And at $\theta_1 = 0 $, we get

$ \cos \phi = \dfrac{1}{2} ( 1 + c ) $

So either $\theta_1 = 0 $ or $\theta_1 = \theta $ will produce the minimum angle $\phi$, which translates into the minimum Euclidean distance between the initial point $(1, 0, 0)$ and the final point.


If we now, however, assume that $\theta_1 \le 0 $ and $\theta_2 \ge 0 $, then from the condition $ | \theta_1 | + | \theta_2 | = \theta $, we get

$ \theta_2 = \theta + \theta_1 $

And this means that

$ c_2 = c c_1 - s s_1 $

$ s_2 = s c_1 + c s_1 $

Hence,

$ p'^T R^T p' = \dfrac{1}{2} (c_2 - s_1 s_2 + c_1) = \dfrac{1}{2} ( c c_1 - s s_1 + c_1 - s_1 ( s c_1 + c s_1) ) $

And this simplifies to

$p'^T R^T p' = \dfrac{1}{2} ( (1 + c) c_1 - s s_1 - s s_1 c_1 - c s_1^2 )$

Taking the derivative and equating to $0$,

$ - (1 + c) \sin(\theta_1) - s \cos(\theta_1) - s \cos( 2 \theta_1) - c \sin(2 \theta_1) = 0 $

And this becomes, after multiplying through by (-1),

$ \sin(\theta_1) + \sin(\theta + \theta_1) + \sin(\theta + 2 \theta_1) = 0 $

Combining the first two terms,

$ 2 \sin \left( \dfrac{\theta}{2} + \theta_1 \right) \left( \cos \left(\dfrac{\theta}{2} \right) + \cos \left( \dfrac{\theta}{2} + \theta_1 \right) \right) = 0 $

And finally this becomes,

$ 4 \sin \left( \dfrac{\theta}{2} + \theta_1 \right) \cos \left(\dfrac{\theta}{2} + \dfrac{\theta_1}{2} \right) \cos \left( \dfrac{\theta_1}{2} \right) = 0 $

So the only possible root is

$ \theta_1 = - \dfrac{\theta}{2} $

The other two factors produce invalid values for $\theta_1$.

The second derivative is given by (remember we previously multiplied by (-1))

$D_2 = - ( \cos(\theta_1) + \cos(\theta + \theta_1) + 2 \cos(\theta+2 \theta_1) $

Evaluating this at $\theta_1 = - \dfrac{\theta}{2} $ gives

$D_2 = - \left( \cos \left( \dfrac{\theta}{2} \right) + \cos \left( \dfrac{\theta}{2} \right) + 2 \right) = - 2 \left(1 + \cos \left( \dfrac{\theta}{2} \right) \right) \lt 0 $

So we have a (local) maximum at $ \theta_1 = - \dfrac{\theta}{2} $

Now let's evaluate the expression $ p'^T R^T p'$, it evaluates to

$ p'^T R^T p' = \dfrac{1}{2} ( (1 + c) c_1 - s s_1 - s s_1 c_1 - c s_1^2 )$

The previous value with $\theta_1 = 0 $ was $\dfrac{1}{2} (1 + c) $

Further analysis (omitted), reveals that the new value is greater, indicating that the new $\phi$ will be smaller (which is expected).

So the conclusion is: For the vector $(1, 0, 0)$, the optimal double rotation is obtained with $\theta_1 = - \dfrac{\theta}{2} $ and $\theta_2 = \dfrac{\theta}{2} $

I've written a very short program to verify these findings, and found that my conclusion matches the output of the program.

$\endgroup$
0
$\begingroup$

The rotation $\theta$ for a point $p$ about an axis $\vec k$ is given according to Rodrigues formula,

$$ R(\vec k,\theta).p = p \cos\theta+\vec k\times p\sin\theta+\vec k\cdot p(1-\cos\theta)p $$

where

$$ R(\vec k,\theta) = \left( \begin{array}{ccc} \cos (\theta )-k_1^2 (\cos (\theta )-1) & -k_1 k_2 ((\cos (\theta )-1))-k_3 \sin (\theta ) & k_2 \sin (\theta )-k_1 k_3 (\cos (\theta )-1) \\ k_3 \sin (\theta )-k_1 k_2 (\cos (\theta )-1) & \cos (\theta )-k_2^2 (\cos (\theta )-1) & -k_1\sin (\theta )-k_2 k_3 (\cos (\theta )-1) \\ -k_2\sin (\theta )-k_1 k_3 (\cos (\theta )-1) & k_1 \sin (\theta )-k_2 k_3 (\cos (\theta )-1) & \cos (\theta )-k_3^2 (\cos (\theta )-1) \\ \end{array} \right) $$

now taking $\vec k = (1,0,1)/\sqrt{2}$ we have

$$ R_1((1,0,1)/\sqrt{2},\theta) = \left( \begin{array}{ccc} \cos ^2\left(\frac{\theta }{2}\right) & -\frac{\sin (\theta )}{\sqrt{2}} & \sin ^2\left(\frac{\theta }{2}\right) \\ \frac{\sin (\theta )}{\sqrt{2}} & \cos (\theta ) & -\frac{\sin (\theta )}{\sqrt{2}} \\ \sin ^2\left(\frac{\theta }{2}\right) & \frac{\sin (\theta )}{\sqrt{2}} & \cos ^2\left(\frac{\theta }{2}\right) \\ \end{array} \right) $$

and with $\vec k = (-1,0,1)/\sqrt{2}$

$$ R_2((-1,0,1)/\sqrt{2},\psi) = \left( \begin{array}{ccc} \cos ^2\left(\frac{\psi }{2}\right) & -\frac{\sin (\psi )}{\sqrt{2}} & \frac{1}{2} (\cos (\psi )-1) \\ \frac{\sin (\psi )}{\sqrt{2}} & \cos (\psi ) & \frac{\sin (\psi )}{\sqrt{2}} \\ \frac{1}{2} (\cos (\psi )-1) & -\frac{\sin (\psi )}{\sqrt{2}} & \cos ^2\left(\frac{\psi }{2}\right) \\ \end{array} \right) $$

now making $p = p_1$ the final distance to calculate is

$$ d^2 = \|R_2R_1 p_1-p_1\|^2 = p_1^TR_1^TR_2^TR_2R_1 p_1-2p_1^TR_1^TR_2^Tp_1+\|p_1\|^2 = 2\|p_1\|^2 - 2p_1^TR_1^TR_2^Tp_1 $$

and the minimum distance is associated to the maximum of $p_1^TR_1^TR_2^Tp_1$. The final formulation can be written as

$$ (\theta^*,\psi^*) = \arg\max_{\theta,\psi}p_1^TR_1(\theta)^TR_2(\psi)^Tp_1\ \ \ \text{s.t.}\ \ \theta+\psi=C $$

NOTE

$R_1,R_2$ are rotations so $R_i^TR_i = I_3$ and

$$ p_1^TR_1(\theta)^TR_2(\psi)^Tp_1=\frac{1}{2} \left(\cos (\theta ) \left(2 y_1^2 \cos (\psi )-\sqrt{2} y_1 \sin (\psi ) (x_1+z_1)+(x_1-z_1)^2\right)-2 \sin \left(\frac{\psi }{2}\right) \sin (\theta ) (x_1-z_1) \left(\cos \left(\frac{\psi }{2}\right) (x_1+z_1)+\sqrt{2} y \sin \left(\frac{\psi }{2}\right)\right)+(x_1+z_1) \left(\cos (\psi ) (x_1+z_1)+\sqrt{2} y \sin (\psi )\right)\right) $$

and considering $p_1 = (1,0,0)$ we have

$$ p_1^TR_1(\theta)^TR_2(\psi)^Tp_1=\frac{1}{2} (\cos (\psi )+\cos (\theta )-\sin (\psi ) \sin (\theta )) $$

$\endgroup$

You must log in to answer this question.

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