Maximum concyclic points Given n points, find an algorithm to get a circle having maximum points.
 A: 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.
A: 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.
