3

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

stWrong
  • 143
  • Is it about finding the largest set of concyclic points? – peterwhy Apr 29 '16 at 22:45
  • To show your effort, do you have any (possibly inefficient) algorithm that solves this problem? – peterwhy Apr 29 '16 at 22:56
  • This is a special case of the problem of finding a maximal-size coplanar subset of $n$ points in 3-space, namely the points $(x_i, y_i, x_i^2 + y_i^2)$ where $(x_i,y_i)$ are the $n$ given points. I don't know whether this problem has a solution more efficient than trying all triples, nor whether one can make any use of the points all lying on the paraboloid $z = x^2 + y^2$. – Noam D. Elkies Apr 30 '16 at 02:28

2 Answers2

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.

Kuifje
  • 9,584
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.

marty cohen
  • 107,799