# 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^2Log N approach.

-
For the sake of those readers not already familiar with the "standard question", perhaps you should include the question statement, either in-line or as a link to a fairly stable resource. –  Willie Wong Feb 3 '11 at 11:42
@Willie: if not supplied, I would vote to close as not a real question –  Ross Millikan Feb 3 '11 at 13:37
But how can you both 'have solved' the problem and not be able to write the precise statement for us? We do not want 'an idea about the problem'. –  Glen Wheeler Feb 3 '11 at 13:44
@Ross and other -Im sorry for not having supplied the text earlier. –  Ravi Kiran Feb 3 '11 at 15:02
Related to Dan's response: the maximum number of colinear points from a set of $N$ given points is obviously $N$. Let me suggest the rephrasing: "You are to find the largest number $M$ such that $M$ of the points from the original $N$ are colinear." You probably find this implicit. –  Glen Wheeler Feb 4 '11 at 8:55

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).

-
I believe sweep-line type algorithms might work for the dual version. Of course, not sure :-) btw, if we were hashing, we could hash the line $y = mx + c \text{ as the pair } (m,c)$, do this $\mathcal{O}(n^2)$ times and count the one with the max hits etc. Without resorting to point-line duality. –  Aryabhata Feb 3 '11 at 17:17
@moron That almost works, but vertical lines cause you some issues. You can use the $ax+by=c$ form and hash as a triplet but then you need to do a bit of fiddling to ensure that you identify e.g. $(a, b, c)$ with $(2a, 2b, 2c)$ - things get mildly tricky since you're dealing with a projective space. :-) –  Steven Stadnicki Feb 3 '11 at 17:45
Also, of course, finding hashing schemes with guaranteed $O(1)$ performance is a remarkably non-trivial matter... –  Steven Stadnicki Feb 3 '11 at 17:46
You could treat the verticals specially without too much trouble. Agree with the hash comment (I never claimed it was $\mathcal{O}(1)$):-) –  Aryabhata Feb 3 '11 at 17:53