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?
Largest set of cocircular points
algorithms;computational geometry