1
$\begingroup$

In Introduction to Algorithms (CLRS), Exercise 33-1-1, we are asked to prove that if $p_1 \times p_2$ is positive then $p_1$ is clockwise from $p_2$ and if it's negative, then $p_1$ is counter-clockwise from $p_2$.

This is a picture from CLRS enter image description here

I found the following proof: https://sites.math.rutgers.edu/~ajl213/CLRS/Ch33.pdf

The proof above says to consider the angles both vectors make with the x-axis. We know the angle is $\arctan y/x$. We also know the cross product $p_1 \times p_2 = x_1y_2 - y_1x_2$. If this product is greater than zero, then this means that $y_2/x_2 > y_1/x_1$. Since $\arctan$ is monotone then the angle $p_2$ makes with the x-axis is larger. which means you need to move clockwise direction to get from $p_2$ to $p_1$

BUT the question is asking to prove that $p_1$ is clockwise relative $p_2$. What am I missing? is the above proof wrong?

I drew the following based on the proof above: enter image description here

$\endgroup$
1
  • $\begingroup$ You have been correct all the time. Except in the very last moment. Instead of "therefore, $p_2$ is clockwise relative to $p_1$", it should have been, "therefore, $p_2$ is counterclockwise relative to $p_1$." (I assume that $x_1>0$ and $x_2>0$ in the illustration.) $\endgroup$ – John L. Apr 14 '20 at 1:42
1
$\begingroup$

In two-dimensional space, $p_1 \times p_2$ is equal to $|p_1||p_2|\sin\theta$, where $\theta$ is the angle from $p_1$ to $p_2$. Depending which textbook you're using, this is probably the definition of the two-dimensional cross product—I'm not sure what definition Introduction to Algorithms uses.

$|p_1|$ and $|p_2|$ both have to be non-negative (by the definition of vector magnitude), so if neither of them is zero, the sign of the whole expression will be the sign of $\sin\theta$.

Now, how do we define "clockwise"? The easiest definition I know is is, $p_1$ is clockwise from $p_2$ if the angle(*) from $p_1$ to $p_2$ is less than 180 degrees. Try a few examples and you'll see how this definition works—remember that angles are traditionally measured with counter-clockwise being positive.

Now, we know that if $p_1 \times p_2$ is positive, then $\sin\theta$ must be positive. And if $\sin\theta$ is positive, then $\theta$ must be less than 180 degrees(*). So by the definition of clockwise, $p_1$ is clockwise from $p_2$.

(*) I'm assuming without loss of generality that all angles are positive and less than 360 degrees.

$\endgroup$

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.