3

at my university, we're doing a project with kinetic datastructures right now, and for that, I need to know at which time point 4 given points become co-circular (in a position such that they are all on one circle).

Let $p_i, p_k, p_j, p_l$ be those points, which form at least a convex quadrilateral (that is guaranteed at this point).

We determined that one way to determine co-circularity is that the sum of opposing inner angles must reach $\pi$. For the opposing angles $\angle d,a,b$ and $\angle b,c,d$.

To simplify calculations, we limit ourselves to the cosine of the angles:

So: $$\cos \angle p_i p_k p_j = 1 - \cos \angle p_i p_l p_j$$

Then, we apply the law of cosines:

$$\cos \angle p'_i p'_k p'_j = \frac{{dist}^2(p'_i,p'_k) + {dist}^2(p'_i,p'_j) - {dist}^2(p'_j,p'_k)} {{dist}(p'_i,p'_k) \cdot {dist}(p'_i,p'_j)}$$

(The other side is similar)

Now, expanding the dist functions, we get:

$$\cos \angle p_i p_k p_j = \frac{\rho^2(x_i-x_k)^2 + (y_i-y_k)^2 + \rho^2(x_j-x_k)^2 + (y_j-y_k)^2 - \rho^2(x_i-x_j)^2 - (y_i-y_j)^2} {\sqrt{\rho^2(x_i-x_k)^2 + (y_i-y_k)^2} \cdot \sqrt{\rho^2(x_j-x_k)^2 + (y_j-y_k)^2}}$$

$$\cos \angle p_i p_l p_j = \frac{\rho^2(x_i-x_l)^2 + (y_i-y_l)^2 + \rho^2(x_j-x_l)^2 + (y_j-y_l)^2 - \rho^2(x_i-x_j)^2 - (y_i-y_j)^2} {\sqrt{\rho^2(x_i-x_l)^2 + (y_i-y_l)^2} \cdot \sqrt{\rho^2(x_j-x_l)^2 + (y_j-y_l)^2}}$$

$\rho$ is the scaling factor.

Replacing these in the first equation, and factoring out $\rho$ where possible:

$$\frac{\rho^2(x_i-x_k)^2 + (y_i-y_k)^2 + \rho^2(x_j-x_k)^2 + (y_j-y_k)^2 - \rho^2(x_i-x_j)^2 - (y_i-y_j)^2} {\sqrt{\rho^2(x_i-x_k)^2 + (y_i-y_k)^2} \cdot \sqrt{\rho^2(x_j-x_k)^2 + (y_j-y_k)^2}} = \\ 1- \frac{\rho^2(x_i-x_l)^2 + (y_i-y_l)^2 + \rho^2(x_j-x_l)^2 + (y_j-y_l)^2 - \rho^2(x_i-x_j)^2 - (y_i-y_j)^2} {\sqrt{\rho^2(x_i-x_l)^2 + (y_i-y_l)^2} \cdot \sqrt{\rho^2(x_j-x_l)^2 + (y_j-y_l)^2}}$$

Aaand... that's where I got stuck. Algebra has never been one of my strong points.

All those $x_i$ and $y_i$ are known, but I need to know $\rho$.

I resolved it once, but then noticed I'd factored out the $\rho$ from the square roots, without noticing that the part with the y-coordinates did not have a $\rho$ factor. Now I'm not sure how to get it out of the square roots.

How to I determine $\rho$? (Or at the very least, I how do I get rid of those square roots?)

user1582024
  • 131
  • Why don't you consider combining an horizontal and a vertical scaling factor. (the horizontal and the vertical factor being independant) ? – Jean Marie Sep 25 '16 at 13:30

1 Answers1

4

Your approach is

  • too complicated (too many square roots!)

  • bound to be not trustworthy because coming from reasoning on angles and can switch suddenly modulo $2 \pi$...

The most classical test that is done for cocircularity is issued from the fact that there exist $a,b,c$ ($(a,b)$ are the center's coordinates, but we do not assume at all that this center is known) such that the general equation of a circle, i.e.,

$$x^2+y^2-2ax-2by+c=0$$

(coming from the expansion of $(x-a)^2+(y-b)^2=R^2$) should be verified by the 4 points, a condition that you can put under the form:

$$\tag{1}\begin{pmatrix}(x_1^2+y_1^2) & x_1 & y_1 & 1\\ (x_2^2+y_2^2) & x_2 & y_2 & 1\\ (x_3^2+y_3^2) & x_3 & y_3 & 1\\ (x_4^4+y_4^2) & x_4 & y_4 & 1 \end{pmatrix}\begin{pmatrix}1\\-2a\\-2b\\c \end{pmatrix}=\begin{pmatrix}0\\0\\0\\0 \end{pmatrix}.$$

(1) expresses that the matrix has a non zero vector in its kernel, a condition that is equivalent to the fact that its determinant is $0.$

In conclusion, the cocircularity condition is:

$$\begin{vmatrix}(x_1^2+y_1^2) & x_1 & y_1 & 1\\ (x_2^2+y_2^2) & x_2 & y_2 & 1\\ (x_3^2+y_3^2) & x_3 & y_3 & 1\\ (x_4^4+y_4^2) & x_4 & y_4 & 1 \end{vmatrix}=0$$

As I understand your problem, you are looking for an horizontal scaling factor $r$ such that

$$\begin{vmatrix}(r^2 x_1^2+y_1^2) & r x_1 & y_1 & 1\\ (r^2 x_2^2+y_2^2) & rx_2 & y_2 & 1\\ (r^2 x_3^2+y_3^2) & r x_3 & y_3 & 1\\ (r^2 x_4^4+y_4^2) & r x_4 & y_4 & 1 \end{vmatrix}=0$$

This gives rise to a 3rd degree equation (in general) that clearly has the following roots:

  • $r=0$ (deprived of any interest, of course).

  • either two opposite real roots $r=\pm r_0$ or 2 complex conjugate roots $r=a\pm ib$ (this last case being neither usable).

Jean Marie
  • 81,803
  • Ah, I knew there must be a better way. I'll see if this works. – user1582024 Sep 25 '16 at 11:16
  • Great answer! +1 – Matthew Leingang Sep 25 '16 at 11:43
  • Though, how can the equation be valid if $r = 0$ is a root? That would yield 4 points on a vertical line, through which you cannot draw a circle. Is that just a quirk of this way of reasoning? – user1582024 Sep 25 '16 at 17:36
  • 1
    Yes, you are right, a kind of spurious solution, but not so spurious because the $y$-axis can be considered as a circle with infinite radius ! – Jean Marie Sep 25 '16 at 18:06
  • Wait a minute... wtf? That's both absolutely crazy and absolutely fascinating. Thank you for clarifying, I learned something. – user1582024 Sep 25 '16 at 18:34
  • The same can be said about solution $-r_0$ with respect to $r_0$: it corresponds to a symmetry with respect to the $y$ axis. – Jean Marie Sep 26 '16 at 04:54
  • Besides, I just found a reference with the adjective "concyclicity" : (http://math.stackexchange.com/q/1252944). There are many answers, not all of them operational. One of them is along your reasoning, another one like mine, and a third one uses the fact that the intersection of the perpendicular bissectors should be the same... (i.e. be the circle"s center). – Jean Marie Sep 26 '16 at 04:58