Find a circle with a minimum distance between it and five known points on R^2

Question

Suppose we have five points $p_i(x_i,y_i)$ $i=1,2,...5$. What is the equation of the circle such that the sum of distances between these five points and the circle (circumference) is a minimum. Observe that the circle may contains some points and some outside it.

Answer 1

This doesn't optimize exactly what you wrote, but it might still be useful.

Suppose for a moment that there were a circle passing through all of these points. In that case, there would be three parameters $a,b,c$ such that $ax+by+c=x^2+y^2$. This corresponds to the more conventional circle equation $(x-\tfrac a2)^2+(y-\tfrac b2)^2=c+\tfrac{a^2}4+\tfrac{b^2}4$ so the center would be at $(\tfrac a2,\tfrac b2)$ and the radius would be $\sqrt{c+\frac{a^2+b^2}4}$. So here you have a linear system of equations:

$$\begin{pmatrix} x_1&y_1&1\\ x_2&y_2&1\\ x_3&y_3&1\\ x_4&y_4&1\\ x_5&y_5&1 \end{pmatrix}\cdot\begin{pmatrix} a\\b\\c \end{pmatrix}=\begin{pmatrix} x_1^2+y_1^2\\ x_2^2+y_2^2\\ x_3^2+y_3^2\\ x_4^2+y_4^2\\ x_5^2+y_5^2 \end{pmatrix}$$

This is overdetermined, so if your five points really were cocircular, you could simply pick any three and compute the required parameters from that. But in your actual situation, these are not really equations, more like $\approx$ instead of $=$.

One way to deal with such an overdetermined system of approximate equations is a least squares approach. Which means finding those parameters $a,b,c$ for which the sum of the squares of all the errors is minimal. You'd do that by taking the left $5\times3$ matrix, transposing it and multiplying that transpose to both sides of the equation. So instead of the vector equation $A\cdot\lambda\approx b$ you solve $A^TA\cdot\lambda=A^Tb$. $A^TA$ is $3\times 3$ so in general that will give you $a,b,c$ just fine.

But what have we actually minimized here? Let's use $e_i$ to denote the error in each of the equations, keeping in mind that we minimized $\sum e_i^2$. The equation which actually holds is $ax+by+c=x^2+y^2+e$ or $ax+by+(c-e)=x^2+y^2$, so the distance to the point is now $\sqrt{c-e+\frac{a^2+b^2}4}$ and hence the distance to the circle is

$$\left\lvert\sqrt{c-e+\frac{a^2+b^2}4}-\sqrt{c+\frac{a^2+b^2}4}\right\rvert$$

Looks pretty complicated, huh? On the other hand, it's easy to see that as $e$ decreases, this distance will decrease, too. So keeping all the $e$ small is a good way to accomplish a good fit.

If you just want a simple way to find a good fit, without really caring about the optimality criterion, I'd go for this. If you are set upon minimizing the distances, you could use this as a starting for some numeric optimization, perhaps using some form of gradient descent. I doubt you can find a simple closed formula for the result in that case, though.

Answer 2

As angryavian commented, an optimal solution will have radius the median of the five distances to the centre. Thus at least one point is on the optimal circle. I suspect that it will usually (but maybe not always) have three points on the circle. If that is the case, the centre is the intersection of the perpendicular bisectors of each pair of those three points. In most of the other cases, I think it will have two points on the circle. In that case, we know the centre is on the perpendicular bisector of those two points. That makes the search space one-dimensional, which makes the search much easier.