1
$\begingroup$

When a circle is defined by three points on its perimeter, it's possible to find its center $(h,k)$ using: $$ h=\frac{\left| \begin{matrix}x_1^2+y_1^2 & y_1 & 1 \\x_2^2+y_2^2 & y_2 & 1 \\ x_3^2+y_3^2 & y_3 & 1\end{matrix} \right|}{2*\left| \begin{matrix}x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{matrix} \right|}, k=\frac{\left| \begin{matrix}x_1 & x_1^2+y_1^2 & 1 \\x_2 & x_2^2+y_2^2 & 1 \\ x_3 & x_3^2+y_3^2 & 1\end{matrix} \right|}{2*\left| \begin{matrix}x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{matrix} \right|} $$ (Taken from here)

But this assumes that the points are defined using real numbers. How should this formula be adapted when the points are defined using rationals with a common denominator? (i.e.: a point is defined using $(a/w, b/w)$).

I noticed that the denominator is the same as when calculating the orientation of three points. In that situation the 1's are replaced by the $w$'s. Is this also true for finding the center? Since the numerator contains squares, what are the implications then for the last column?

Update: Based on @saulspatz answer I think the following is correct:

My actual situation is as follows (only for $h$): $$ h=\frac{\left| \begin{matrix}\frac{x_1}{w_1}^2+\frac{y_1}{w_1}^2 & \frac{y_1}{w_1} & 1 \\\frac{x_2}{w_2}^2+\frac{y_2}{w_2}^2 & \frac{y_2}{w_2} & 1 \\ \frac{x_3}{w_3}^2+\frac{y_3}{w_3}^2 & \frac{y_3}{w_3} & 1\end{matrix} \right|}{2*\left| \begin{matrix}\frac{x_1}{w_1} & \frac{y_1}{w_1} & 1 \\ \frac{x_2}{w_2} & \frac{y_2}{w_2} & 1 \\ \frac{x_3}{w_3} & \frac{y_3}{w_3} & 1 \end{matrix} \right|} $$

When I now multiply each row by its corresponding $w$ I have to correct the determinant by dividing by the same factor: $$ h=\frac{\frac{1}{w_1^2w_2^2w_3^2}\left| \begin{matrix}x_1^2+y_1^2 & y_1w_1 & w_1^2 \\x_2^2+y_2^2 & y_2w_2 & w_2^2 \\ x_3^2+y_3^2 & y_3w_3 & w_3^2\end{matrix} \right|}{\frac{2}{w_1w_2w_3}\left| \begin{matrix}x_1 & y_1 & w_1 \\ x_2 & y_2 & w_2 \\ x_3 & y_3 & w_3 \end{matrix} \right|} $$

I now multiply by $w_1^2w_2^2w_3^2$, which leaves: $$ h=\frac{\left| \begin{matrix}x_1^2+y_1^2 & y_1w_1 & w_1^2 \\x_2^2+y_2^2 & y_2w_2 & w_2^2 \\ x_3^2+y_3^2 & y_3w_3 & w_3^2\end{matrix} \right|}{2w_1w_2w_3\left| \begin{matrix}x_1 & y_1 & w_1 \\ x_2 & y_2 & w_2 \\ x_3 & y_3 & w_3 \end{matrix} \right|} $$

$\endgroup$
2
$\begingroup$

If you multiply a column of a determinant by $c$ the determinant is also multiplied by $c$. So if we say that the points are $(\frac{x_k}{w}, \frac{y_k}{w})$ the values would become $$ h=\frac{\frac{1}{w^3} \left|\begin{matrix}x_1^2+y_1^2 & y_1 & 1 \\x_2^2+y_2^2 & y_2 & 1 \\ x_3^2+y_3^2 & y_3 & 1\end{matrix} \right|}{\frac{2}{w^2}\left| \begin{matrix}x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{matrix} \right|}, k=\frac{\frac{1}{w^3}\left| \begin{matrix}x_1 & x_1^2+y_1^2 & 1 \\x_2 & x_2^2+y_2^2 & 1 \\ x_3 & x_3^2+y_3^2 & 1\end{matrix} \right|}{\frac{2}{w^2}\left| \begin{matrix}x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{matrix} \right|}$$ Now after multiplying numerator and denominator by $w^3$, you could bring the the $w$ inside the determinant by multiplying the last column by $w$. That would make the last column $w$, but only in the denominators.

$\endgroup$
  • $\begingroup$ Each of my points has a different $w$. I've updated my question where I multiply each row with a factor instead of each column. I think this is correct as well. I'm happy to accept your answer as correct, since you gave me the needed insight. $\endgroup$ – Remco Poelstra Apr 10 '18 at 11:40
  • $\begingroup$ You just have to put them all over a common denominator. $\endgroup$ – saulspatz Apr 10 '18 at 12:27
  • $\begingroup$ I'm unsure what you mean. Is my update not correct? $\endgroup$ – Remco Poelstra Apr 10 '18 at 12:35
1
$\begingroup$

The calculation/formula is exactly the same for rational values of the entries.

Your profile suggests that you want to do this in a computer program. To get an exact rational answer rather than a floating point approximation you will have to do rational number arithmetic. Some languages implement this for you.

The squares don't cause a problem - they are rational. If you needed square roots you'd be in trouble.

$\endgroup$
  • $\begingroup$ Yes, I need it in a computer program :). Rational calculations are not directly the problem. It's a problem however to use $a/w$ for $x$ (and similar for $y$) as that involves a lot of computations. The beauty of the above formula would be that it results in a rational point if I could solve the determinants using only multiply and add/subtract. Much like the orientation problem can be solved by replacing the last column using the $w$ values. $\endgroup$ – Remco Poelstra Apr 9 '18 at 15:49
  • $\begingroup$ @saulspatz answer shows you how to calculate the determinants using only integer arithmetic by factoring out a common denominator. $\endgroup$ – Ethan Bolker Apr 9 '18 at 15:56

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.