How to tell if up to floating point round-off, 4 2-d points might lie on a common circle?

Question

So a friend of mine is writing a supposed test on 4 2-d floating point tuples (say IEEE 64-bit, which I believe is the case), where the test should report "false" if it is impossible with floating point round-off error (on each float independently) for the 4 2-d points to be on a common circle, otherwise report "maybe/true". He claims that he is generating 4 random floating point pairs on a circle by setting the center of the circle to be (0,0) and then choosing a random global radius and then choosing uniform random angles for each 2-d point, and using cos/sin to get x and y for each point, and often his test is reporting "false", i.e. the resulting 4 floating point pairs supposedly could not be explained as being on a common circle, up to independent rounding error for each float.

My friend's code is proprietary at his company so he can't share it with me, but it got me wondering. How would one determine whether 4 2-d points defined by 64-bit IEEE floats might lie on a common circle, assuming that each float was subject to independent finite precision rounding? And is my friend's testing procedure paradigm valid for such a function? Or might he being generating examples whose answer he thinks should be "true/maybe" but whose actual answer, according to the definition I have given, should be "false"?

Answer 1

The challenge is to find the center of the circle. This is straightforward if you recognize the following fact.

Draw two points on a circle. As both points must be one radius away from the center, that means the center must lie on the line perpendicular to their midpoint.

That is if I gave you points (1, 1) and (1,3), if the points are on a common circle it the center must be on the line y=2.

Or in general if I gave you points P1 = (x1, y1) and P2 = (x2, y2), then the midpoint is P_mid = (x_mid, y_mid) = (0.5*(x1+x2), 0.5*(y1+y2)). The slope of the line between the two given points is m = (y2 - y1)/(x2 - x1), so the slope of the perpendicular line is m_perp = - (x2 - x1)/(y2 - y1). Therefore the equation of the line that the center must fall on if (x1, y1) and (x2, y2) fall on the same line is y = m_perp ( x - x_mid) + y_mid.

Now we have 4 points given to us. Every pair of points gives us a line of intersection. There are six pairs of points (P1, P2), (P1, P3), (P1, P4), (P2, P3), (P2, P4), (P3, P4). Each pair of points gives us a line that the center must fall on. Take any two of these lines and you can solve for the center P_center by finding where the lines intersect (you have two equations and two unknowns). Now simply calculate the distance from each point to the calculated center, and make sure all of these distances fall within some allowed floating point tolerance (e.g., 1e-14 for 64-bit floats).