Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
@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

3 Answers 3

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

share|improve this answer
    
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

The maximum number of collinear points among N points in a plane is N (i.e., if they happen to be collinear.)

share|improve this answer
    
They explanation in brackets is to help understand the collinear property.It isn't given that they are collinear already. –  Ravi Kiran Feb 3 '11 at 16:16
    
I might have answered the same, Ravi. Dan is pointing out that the usage of the word "maximum" is wrong. –  Glen Wheeler Feb 4 '11 at 8:46

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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