3
$\begingroup$

Given three circles centered at points $A$, $B$, and $C$ with non-zero radii of lengths $R_A$, $R_B$ and $R_C$. Where the centers of the circles form a valid triangle, and where the distance between any two centers is less than or equal to the sum of their corresponding radii.

Question: Is it possible to determine if all three circles intersect at a common point using a calculation simpler than first determining the pair of intersection points between two pairs of circles then determining if any of the intersection points are equal?

$\endgroup$
2
$\begingroup$

You can calculate the pair of intersection between, say, circles $A$ and $B$, then calculate the distance of each such intersection to circle $C$. There is a triple intersection if and only if one of the distances is $R_C$.

EDIT: Well, consider $\triangle ABC$ and suppose there is a triple intersection, that is, some point $P$ with $PA=R_A$, $PB=R_B$ and $PC=R_C$. Let $E_A$ be the side of $\triangle ABC$ opposite vertex $A$ and similarly for $B$ and $C$.

Suppose without loss of generality that $R_A\leq R_B\leq R_C$. The triangle inequality implies that the following must hold:

\begin{align} R_C-R_B\leq E_A\leq R_C+R_B\\ R_C-R_A\leq E_B\leq R_C+R_A\\ R_B-R_A\leq E_C\leq R_B+R_A \end{align}

By hypothesis, the right hand inequalities do hold, but if any of the left hand ones do not, you can already rule out the possibility of a triple intersection.

I might yet improve on this later.

$\endgroup$
  • $\begingroup$ +1 Interesting solution and it is better than two sets of intersection pairs. Though I was hoping for a solution based around perhaps the triangle constructed from the centers and some constraint based on lengths of the edges and the radii - if nothing better comes along I'll set this as the answer. $\endgroup$ – Sari T. Mar 5 '17 at 1:47
  • $\begingroup$ See the edit. ${}$ $\endgroup$ – Fimpellizieri Mar 5 '17 at 2:36
  • $\begingroup$ That is a much simpler and cheaper calculation to verify than the first suggestion and I'm already performing some of those lengths as part of the initial proper triangle verification stage. $\endgroup$ – Sari T. Mar 5 '17 at 2:43
  • $\begingroup$ Yes, but notice that the inequalities being satisfied does not imply the existence of a triple intersection. Well, at least, I haven't proved that. $\endgroup$ – Fimpellizieri Mar 5 '17 at 2:48
  • $\begingroup$ oh I misunderstood. What then would it require to prove that if those inequalities hold there is indeed a triple intersection? $\endgroup$ – Sari T. Mar 5 '17 at 2:58
2
$\begingroup$

Don't know that it's much simpler than calculating the pairwise intersections, then the distances to the third center, but the following gives a symmetric condition using complex numbers.

Let $\,a,b,c\,$ be the complex numbers associated with points $A,B,C$ in a complex plane centered at the centroid of $ABC\,$, so that $a+b+c=0\,$.

The point of intersection $z$ of the three circles (if it exists) must satisfy the $3$ equations similar to:

$$ |z-a|^2=R_A^2 \;\;\iff\;\;(z-a)(\bar z - \bar a) = R_A^2 \;\;\iff\;\;|z|^2 - z \bar a - \bar z a + |a|^2 = R_A^2 \tag{1} $$

Writing $(1)$ for $a,b,c$ and summing the $3$ equations up:

$$ \require{cancel} 3\,|z|^2 - \cancel{z \sum_{cyc} \bar a} - \bcancel{\bar z \sum_{cyc} a} + \sum_{cyc}|a|^2 = \sum_{cyc} R_A^2 \;\;\implies\;\; |z|^2 = \frac{1}{3}\left(\sum_{cyc} R_A^2-\sum_{cyc}|a|^2\right) =R^2 \tag{2} $$

Substituting $(2)$ back into each of $(1)\,$:

$$ -|z|^2 + z \bar a + \bar z a - |a|^2 = - R_A^2 \;\;\iff\;\; z \cdot \bar a + \bar z \cdot a = |a|^2+R^2-R_A^2 \tag{3} $$

Considering $(3)$ as a system of linear equations in $z, \bar z\,$, the condition for it to have solutions is:

$$ \left| \begin{matrix} \;\bar a \;&\; a \;&\; |a|^2+R^2-R_A^2\; \\ \;\bar b \;&\; b \;&\; |b|^2+R^2-R_B^2\; \\ \;\bar c \;&\; c \;&\; |c|^2+R^2-R_C^2\; \end{matrix} \right| \;\;=\;\; 0 $$

$\endgroup$
1
$\begingroup$

If we coordinatize, say, with $$A = (0,0) \qquad B = (c, 0) \qquad c = (b\cos A,b\sin A)$$ and take suppose circles $\bigcirc A$, $\bigcirc B$, $\bigcirc C$ (of respective radii $r_A$, $r_B$, $r_C$) meet at a point $P = (x,y)$, then we have three equations in two unknowns $x$ and $y$: $$\begin{align} x^2 + y^2 &= r_A^2 \\ x^2 + y^2 &= r_B^2 + 2 c x - c^2 \\ x^2 + y^2 &= r_C^2 + 2 b x \cos A x + 2 b y \sin A - b^2 \end{align}$$ We can eliminate $x$ and $y$ from these equations, leaving this relation: $$\begin{align} a^2 b^2 c^2 + a^2 r_A^4 + b^2 r_B^4 + c^2 r_C^4 &= \left( a^2 r_A^2 + r_B^2 r_C^2 \right) \left(-a^2 + b^2 + c^2 \right) \\ &+ \left( b^2 r_B^2 + r_C^2 r_A^2 \right) \left(\phantom{-}a^2 - b^2 + c^2 \right)\\ &+ \left( c^2 r_C^2 + r_A^2 r_B^2 \right) \left(\phantom{-}a^2 + b^2 - c^2 \right) \end{align} \tag{1}$$

The right-hand side seems to want to be re-written with cosines ...

$$\begin{align} a^2 b^2 c^2 + a^2 r_A^4 + b^2 r_B^4 + c^2 r_C^4 &= 2 b c \cos A \left( a^2 r_A^2 + r_B^2 r_C^2 \right) \\ &+ 2 c a \cos B \left( b^2 r_B^2 + r_C^2 r_A^2 \right)\\ &+ 2 a b \cos C \left( c^2 r_C^2 + r_A^2 r_B^2 \right) \end{align} \tag{2}$$ ... but this doesn't seem a great deal better. Perhaps if we use the Law of Sines to write $$a = 2 r \sin A \qquad b = 2 r \sin B \qquad c = 2 r \sin C$$ where $r$ is the circumradius of $\triangle ABC$. With a little effort, we find this form for the relation:

$$\begin{align} \frac{1}{64} \left(\;\begin{array}{c} r_A^2 \sin 2A + r_B^2 \sin 2B + r_C^2 \sin 2C \\ - 8 r^2 \sin A \sin B \sin C\end{array} \;\right)^2 = \frac{1}{16}&(\phantom{-}r_A \sin A + r_B \sin B + r_C \sin C ) \\ \cdot &(-r_A \sin A + r_B \sin B + r_C \sin C )\\ \cdot &(\phantom{-}r_A \sin A - r_B \sin B + r_C \sin C )\\ \cdot &(\phantom{-}r_A \sin A + r_B \sin B - r_C \sin C ) \end{align} \tag{3} $$

The curious fractional coefficients are there to help us recognize the right-hand side as Heron's Formula for the square of the area of a triangle with side-lengths $r_A \sin A$, $r_B \sin B$, $r_C \sin C$. More precisely, when (and only when) the right-hand side of $(3)$ is non-negative, it gives the square of the area of the triangle with those side-lengths; when (and only when) the right-hand side is negative, those side-lengths fail to form a valid triangle. (Note: I consider a degenerate triangle of area $0$ to be valid.)

Since the left-hand side of $(3)$ is necessarily non-negative, we deduce that

$\bigcirc A$, $\bigcirc B$, $\bigcirc C$, with radii $r_A$, $r_B$, $r_C$, concur at a point only if $r_A \sin A$, $r_B \sin B$, $r_C \sin C$ are the edges of a valid triangle (ie, they satisfy the Triangle Inequality).

That gives you a way to weed-out bad candidates. To know for sure that the three circles concur, you'd need to check the full equality of $(3)$. (Is that "simpler" than the strategy you mentioned? I'm not sure.)


Note that $8 r^2 \sin A\sin B\sin C = 2 a b \sin C = 4 |\triangle ABC|$. If we call the "valid triangle" referenced above, say, $\triangle T$, then we can write $(3)$ as

$$r_A^2 \sin 2A + r_B^2 \sin 2B + r_C^2 \sin 2C \pm 8 |\triangle T|\;=\; 4 |\triangle ABC| \tag{4}$$

To get at the behavior of the "$\pm$", consider $P$ at distance $p$ from the circumcenter of $\triangle ABC$ (and at distances $r_A$, $r_B$, $r_C$ from $A$, $B$, $C$, respectively). With the help of Mathematica, we get $$\begin{align} r_A^2 \sin 2A + r_B^2 \sin 2B + r_C^2 \sin 2C &= 4 (r^2 + p^2) \sin A \sin B \sin C \\ 8|\triangle T| &= 4 |r^2-p^2|\sin A \sin B \sin C \end{align}$$

We see, then, that "$\pm$" must be "$+$" when $r > p$ (that is, when $P$ is inside the circumcircle) and "$-$" when $r < p$ (when $P$ is outside the circumcircle); for $P$ on the circumcircle, $|\triangle T| = 0$.

$\endgroup$
  • $\begingroup$ Your discussion is quiet interesting and still trying to understand it will take me some time, but using the naive approach of two sets of pairs of intersection requires only 29 operations (15 add/sub operations 14 mul/div operations, 6 comparisons). $\endgroup$ – Sari T. Mar 5 '17 at 5:05
  • 1
    $\begingroup$ If facts about $\triangle ABC$ (sines, cosines, appropriate multiples of area) are pre-computed, then $(3)$ can be written to require at most 27 operations. Note: If $r_A\sin A$, etc, fail to make a valid triangle, then you'll know this by computing the product of final three factors of the RHS of $(3)$ and comparing it to $0$. That's 12 operations. If you compare the individual factors against $0$ along the way (any negative implies failure), you add two comparisons, but you could get lucky and detect failure in just 6 operations. (The total count of 27 includes the extra two comparisons.) $\endgroup$ – Blue Mar 5 '17 at 6:17

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.