How to check if a set of points in cartesian space could lie on the circumference of a circle?

Question

Given x amount of points in Cartesian Space, how would one go about proving or disproving that there exists a circle whose perimeter passes through all of these points?

I don't believe that there's a one or two step, simple answer so even a rough explanation of an algorithm that could conquer this would be much appreciated.

Answer 1

Four points $A,B,C,D$ lie on a circle if and only if the following three conditions are satisfied:

• There is a plane passing through all four points.
• There is not a line passing though all four points.
• The distances between pairs of points satisfy one of the three equalities $AB\cdot CD+AC\cdot BD=AD\cdot BC$, $AB\cdot CD+AD\cdot BC=AC\cdot BD$, or $AC\cdot BD+AD\cdot BC=AB\cdot CD$. This condition is Ptolemy's theorem for cyclic quadrilaterals.

For more than four points? A set of $n$ points with $n\ge 4$ lie on a circle if each subset of four of them lies on a circle. After all, any three of them determine a circle. Two quartets that share three members thus lie on the same circle, making all five points involved lie on that circle; repeat to get all of the points.

Answer 2

Partial answer: Four points forming a convex quadrangle lie an a circle iff the sum of opposite angles equals $\pi$. That may be easily checked with inner product and extended to an arbitrary number of points.

EDIT: Alternatively let $(x,y)$ be the center of the circumscribed circle of three points $P_i(x_i,y_i)$ for $i=1,2,3$. Define $d_i=x_i^2+y_i^2$ and $$D=2\det\begin{pmatrix} x_1 & y_1 & 1\\ x_2 & y_2 & 1\\ x_3 & y_3 & 1 \end{pmatrix},$$ $$D_x=\det\begin{pmatrix} d_1 & y_1 & 1\\ d_2 & y_2 & 1\\ d_3 & y_3 & 1 \end{pmatrix},$$ $$D_y=\det\begin{pmatrix} x_1 & d_1 & 1\\ x_2 & d_2 & 1\\ x_3 & d_3 & 1 \end{pmatrix}.$$

Then $x=D_x/D$ and $y=D_y/D$. From here the center of the circumscribed circle of each triplet of points may be calculated as well as the radius.

Answer 3

Let propose a straightforward method, valid for any number of points $n\geq 3$.

The given data is $$(x_1,y_1)\: , \:(x_2,y_2)\; , … , \:(x_k,y_k)\; , … , \:(x_n,y_n).$$

FIRST, proceed to a circular regression (Formulas below). This leads to $a$ , $b$ , $R$ .

SECOND, for each point : $$\epsilon_k= (x_k-a)^2+(y-b)^2-R^2$$ RESULT :

If all $\epsilon_k=0$ then all points lie on the circle of equation $(x-a)^2+(y-b)^2=R^2$.

Circular regression, from https://fr.scribd.com/doc/14819165/Regressions-coniques-quadriques-circulaire-spherique

SIMPLIFIED METHOD :

Take only three points, for example $(x_1,y_1)$ , $(x_2,y_2)$ , $(x_3,y_3)$

They lie on the circle center $a,b$, radius $R$ given by the same above formulas in setting $n=3$.

Then check if all other points lie on the circle (same method as above).

NOTE :

The equations are analytically exact, not approximate.

Of course the simplest checking is numerical. But all can be carried out analytically.