Maximum concyclic points

Question

Given n points, find an algorithm to get a circle having maximum points.

Answer 1

The method of choosing all sets of 3 points, finding the circle that passes through that set, and seeing which other points lie on that circle has one big problem: roundoff error.

If you try to use any method that involves taking square roots, roundoff can cause problems.

Here is a method, based on some previous work of mine, that allows this to be done without any error, assuming that the points all have rational coordinates.

All operations in the following are assumed to be done with exact rational arithmetic.

Do the following for all sets of three points. Some optimizations can be done by keeping track of when a point is found to be on a circle passing through a set of three points.

Let the points be $(x_i, y_i), i=1, 2, 3 $.

Let the circle be $(x-a)^2+(y-b)^2 =r^2 $ or $x^2-2ax+y^2-2by =r^2-a^2-b^2 $ or $2ax+2by+c =x^2+y^2 $ where $c = a^2+b^2-r^2 $.

Solve the linear system $2ax_i+2by_i+c =x_i^2+y_i^2 , i=1,2,3 $ for $a, b, c$ exactly, using rational arithmetic. If there is no solution, try the next trio.

Then, for every other point $(x, y)$, check if $2ax+2by+c =x^2+y^2 $. If so, the point is on the circle. As before, this can be done exactly with rational arithmetic.

At every stage, keep track of the set of three points that has the most points on its circle.

If you use $O(n^3)$ storage, you can keep track of all previous computation.

At the end, you will have the circle with most points on it.

Answer 2

A possible (non linear) model for this problem:

Define the following variables :

• $a$ is the $x$-coordinate of the circle
• $b$ is the $y$-coordinate of the circle
• $r\ge0\;$ is the radius of the circle
• $\omega_i$ is a binary variable that equals $1$ if and only if point $(x_i,y_i)$ lies on the circle.

The objective function is then to maximize $$ \sum_{i=1}^n \omega_i $$ subject to $$ (x_i-a)^2+(y_i-b)^2\le r^2 +M(1-\omega_i)\quad \forall i=1,\cdots,n\\ (x_i-a)^2+(y_i-b)^2\ge r^2 -M(1-\omega_i)\quad \forall i=1,\cdots,n\\ r\ge 0\\ \omega_i\in\{0,1\}\quad \forall i=1,\cdots,n\\ $$ $M$ is a large constant.   This approach is simple, but it will (probably) not be efficient if you are dealing with a lot of points.