31
$\begingroup$

Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior).

This can be done in $O(n^3)$ easily by trying $\binom{n}{3}$ combinations of points and counting the number of occurrences of all circles found with hash tables.

Question: Is there an algorithm with $o(n^3)$ time?

Bonus question: Is there an algorithm which has a better performance than $O(n^3)$ assuming the maximum size of the (individual) coordinates is $c\times w$ where $w$ is the size of a machine Word and $c$ a constant?

$\endgroup$
11
  • 1
    $\begingroup$ You might want to rethink this as an image processing/computer vision-type problem. IIRC there are scale-invariant versions of the Circle Hough Transform, for example. $\endgroup$
    – Pseudonym
    Commented Nov 11, 2015 at 23:35
  • $\begingroup$ @Pseudonym Hm.. the Wikipedia article mentions that for unknown radius "we can iterate through possible radiuses and for each radius", so the huge downside of that method would be that the complexity is now around $O(NM^2)$ , where $M$ is the maximum magnitude of a coordinate. But maybe there is some way to get something out of image processing. $\endgroup$
    – chubakueno
    Commented Nov 12, 2015 at 2:19
  • $\begingroup$ Yes, you'd probably want some more current research. By the way, if this is a real-world problem that you're trying to solve, don't forget randomised algorithms, like RANSAC and its variants. $\endgroup$
    – Pseudonym
    Commented Nov 12, 2015 at 2:44
  • 8
    $\begingroup$ My guess is no. A lower bound may perhaps be found using the projection here. Project $(x_i,y_i)$ to $(x_i,y_i,x_i^2+y_i^2)$, so that three points are concyclic iff their projections are coplanar. So an $o(n^3)$ test for concylicity reduces to one for coplanarity. $\endgroup$
    – PKG
    Commented Nov 13, 2015 at 1:31
  • 1
    $\begingroup$ Just to note that we do have $o(n^3)$ algorithms that solves the corresponding problem when circles are replaced by lines and cocircular by collinear $\endgroup$
    – John L.
    Commented Aug 9, 2018 at 10:14

1 Answer 1

0
$\begingroup$

About the bonus question: if coordinates are somehow bounded and integer, there is a finite amount of possible coordinates to test. We can create a finite constant set of all the possible useful circles with their respective set of integer points lying in our bounded lattice (this is finite because there are at most $\text{grid size} \choose 3$ of them). Now create a matrix of lists, one per coordinate, and map each point to its respective list in the matrix. Iterate now the constant set of circles and their respective set of coordinates, and count how many of the given points are included. This can be implemented in $O(n)$.

$\endgroup$
2
  • $\begingroup$ Of course, the constant will be impractically big for any realistic scenario. $\endgroup$
    – izanbf1803
    Commented Apr 27 at 22:39
  • $\begingroup$ I don't think this is helpful. A solution with such a large "constant" factor is unrealistic, and I'm not sure it is reasonable/helpful to consider that factor a "constant" any longer. See en.wikipedia.org/wiki/Transdichotomous_model for one standard model of computation for analyzing such algorithms that tries to avoid such cases. $\endgroup$
    – D.W.
    Commented Apr 28 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.