maximum number of collinear points? I know this is a very standard question widely popular in the Internet and the Mathworld.
I myself have solved the above problem is $N^2 \log N$ avoiding floating arithmetic.However, can anyone give me a good resource/detailed explanation of how it can be solved in $O(N^2)$ using point line duality concepts.
Sorry to create such a confusion regarding the statement.
The text would be:
"$N$ different points with integer coordinates are given in a plane. You are to write a program that finds the maximum number of collinear points (they all belong to the same line)."
You may also refer to this site which is the problem I have solved using a $N^2\log N$ approach.
 A: By point-line duality, this is equivalent to the question 'given a configuration of $n$ lines in the plane, what is the maximum number of them which intersect at one point?'; since there are $O(n^2)$ pairwise intersection checks, it becomes a question of whether there's some bucketing/perfect hashing scheme that allows for finding a point in a dynamically-built list in $O(1)$ time.  While I don't know of any specific bucketing schemes applicable to this problem, AFAIK it's very common to have $O(1)$ or at least $O(\alpha(n))$ approaches for this sort of thing ($\alpha(n)$ being the inverse-Ackermann function).
A: Take a look at the two methods described in http://www.cs.princeton.edu/courses/archive/spring03/cs226/assignments/lines.html .
To find 4 or more collinear points given $N$ points, the brute-force method has a time complexity of $\mathcal{O}(N^4)$, but a better method does it in $\mathcal{O}(N^2 \log N)$.
A: The maximum number of collinear points among N points in a plane is N (i.e., if they happen to be collinear.)
