20
$\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$
  • $\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 Nov 11 '15 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 Nov 12 '15 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 Nov 12 '15 at 2:44
  • 4
    $\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 Nov 13 '15 at 1:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.