## The Complex Beauty of Simplicity

As I have said before, some of my friends took the very wise decision to go back to school (that is, university) and, accordingly, they’re doing all the undergrad maths courses. As I try to help them whenever I can, I decided to ask them to solve a simple puzzle… or so I thought.

So the problem is as follows:

You have a circle of center $C$, radius $r\geqslant{}0$ and some point $Z$, with $Z\neq{}C$. Find the projection $P$ of point $Z$ against the circle with center $C$ and radius $r$. The method should work whether $Z$ is inside or outside the circle.

So I ask Ethan (that’s not his real name, but he’ll recognize himself) to solve this problem. So he thinks about this a few seconds and sets to solve the two equations, two unknowns system:

$(P_x-C_x)^2+(P_y-C_y)^2=r^2$

$\displaystyle{\frac{P_y-C_y}{P_x-C_x}=\frac{Z_y-C_y}{Z_x-C_x}}$

which is non-linear. Of course, I stopped him right there to spare him the pain of solving it, because that’s not the solution I was thinking of. But for you, let’s work out the solution anyways; you’ll see why.

Since we have $O(x^2)$ terms here and there, let us change the system to:

$(P_x-C_x)^2+(P_y-C_y)^2=r^2$

$\displaystyle{\frac{(P_y-C_y)^2}{(P_x-C_x)^2}=\frac{(Z_y-C_y)^2}{(Z_x-C_x)^2}}$

So we can rewrite the first as either:

$(P_y-C_y)^2=r^2-(P_x-C_x)^2$

or

$(P_x-C_x)^2=r^2-(P_y-C_y)^2$

Let us use the first variant. We can rewrite the second eq. as:

$\displaystyle{\frac{r^2-(P_x-C_x)^2}{(P_x-C_x)^2}=\frac{(Z_y-C_y)^2}{(Z_x-C_x)^2}}$

and let us observe that the right hand side of the equation is constant, as it doesn’t have terms in $P$, for which we are trying to solve. Let us put $a=Z_y-C_y$ and $b=Z_x-C_x$. We can rewrite the equation as:

$\displaystyle{\frac{r^2-(P_x-C_x)^2}{(P_x-C_x)^2}=\frac{a^2}{b^2}}$

let us simplify:

$r^2-(P_x-C_x)^2=\displaystyle\frac{a^2}{b^2}(P_x-C_x)^2$

$r^2=\displaystyle\frac{a^2}{b^2}(P_x-C_x)^2+(P_x-C_x)^2$

$r^2=\displaystyle\frac{a^2}{b^2}(P_x-C_x)^2+(P_x-C_x)^2$

$r^2=\left(1+\displaystyle\frac{a^2}{b^2}\right)(P_x-C_x)^2$

$\frac{r^2}{1+\displaystyle\frac{a^2}{b^2}}=(P_x-C_x)^2$ (*)

$\displaystyle\sqrt{\frac{r^2}{1+\frac{a^2}{b^2}}}=P_x-C_x$

$P_x=C_x+\displaystyle\sqrt{\frac{r^2}{1+\frac{a^2}{b^2}}}$

Wow. That was a lot to find just $P_x$. So we use (*) to solve for $P_y$:

$(P_x-C_x)^2+(P_y-C_y)^2=r^2$

$(P_y-C_y)^2=r^2-(P_x-C_x)^2$

$(P_y-C_y)^2=r^2-\displaystyle\frac{r^2}{1+\frac{a^2}{b^2}}$

$P_y-C_y=\displaystyle\sqrt{r^2-\frac{r^2}{1+\frac{a^2}{b^2}}}$

$P_y=C_y+\displaystyle\sqrt{r^2-\frac{r^2}{1+\frac{a^2}{b^2}}}$

And we’re done. We can quickly check that it’s the right answer (it always helps):

$(P_x-C_x)^2+(P_y-C_y)^2=r^2$

$\left(C_x+\sqrt{\frac{r^2}{1+\frac{a^2}{b^2}}}-C_x\right)^2+ \left(C_y+\sqrt{r^2-\frac{r^2}{1+\frac{a^2}{b^2}}}-C_y\right)^2=r^2$

The $C_x$ and $C_y$ cancel out:

$\left(\sqrt{\frac{r^2}{1+\frac{a^2}{b^2}}}\right)^2+\left(\sqrt{r^2-\frac{r^2}{1+\frac{a^2}{b^2}}}\right)^2=r^2$

$\frac{r^2}{1+\displaystyle\frac{a^2}{b^2}}+r^2-\frac{r^2}{1+\displaystyle\frac{a^2}{b^2}}=r^2$

$r^2=r^2$

So it’s the right solution. Plotting the point $P$ does land on the circumference of the circle (as shown in the illustration above).

*
* *

OK, that’s an insane amount of work for the actual complexity of the problem. Let us now solve it again, but using vectors. Let:

$\vec{Z}=Z-C$

and again, $r$ is a scalar, the radius of the circle. The vector $\vec{Z}$ is parallel (and points in the same direction) to the vector $\vec{P}=P-C$, $P$ being the point we want to solve for. We know that $||\vec{P}||$, the length of $\vec{P}$ is $r$. And points in the same direction as $\vec{Z}$. So let us scale $\vec{Z}$ to length $r$:

$\displaystyle\frac{\vec{Z}}{||\vec{z}||}r$

and, finally:

$P = C+\displaystyle\frac{\vec{Z}}{||\vec{z}||}r$

Which is the right answer as well. That’s the solution I was looking for when I submitted this ‘puzzle’ to my friends.

*
* *

So The second solution is much better than the first one. First, it doesn’t require that $P_x\neq{}C_x$ nor $P_y\neq{}C_y$. Second, it doesn’t require solving an equation system. The most (computationally) complex step is to compute the length of $\vec{Z}$ which is only the euclidean distance between points $C$ and $Z$, given by

$\|Z-C\|=\displaystyle\sqrt{(Z_x-C_x)^2+(Z_y-C_y)^2}$

in 2D. Also, the solution is more general than the first one. Replace ‘circle’ by sphere, and 2D points by 3D points, and the expression for the solution remains the same. It remains the same regardless of the number of dimensions (except zero), actually.

The morale of this is that, sometimes, we must take a step back and look at the problem with a broader view, and use all of our knowledge to find the best possible solution, not just use the tools we are mentally more used to. For Ethan, solving the equation system was the natural way of proceeding, because that’s what he understood best. For me, it was the vector approach, because the formulation was, from the start, a vector-type problem: points, projection, etc. In many cases, the formulation of the problem will influence the way we will try to solve it and that’s why it’s so hard to come up with paradigm-shifting ideas; the mind-set for a problem can be so deeply set into one paradigm that it seems impossible to reformulate it in another and, once that it’s done, solve with more ease it using the other paradigm.

I think it applies to all sorts of problems, not only math problems. Algorithms. Programming. Life in general.