4
$\begingroup$

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.

  • 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.2011-02-03
  • 1
    @Willie: if not supplied, I would vote to close as not a real question2011-02-03
  • 0
    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'.2011-02-03
  • 1
    @Ross and other -Im sorry for not having supplied the text earlier.2011-02-03
  • 0
    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.2011-02-04

3 Answers 3