How to determine the max number of points on the same line?

Question

Given: a lot of points each with a unique coordinate (x_i,y_i)

Output: Max number of points on the same line

This is my method:

for i=1..n
    for j=i..n
        get the line determined by point[i] and point[j]
        for k=1..n
            check if point[k] is on this line

But it seems this method takes too much time and always exceeds the time limit on the OJ system.

can u please post ur code in a formatted manner? exact code which u are using currently would be a plus — mihirj, Jan 25 '13 at 06:31
@mihirj I'm really sorry, I didn't find a way to add linebreaks in my code. — CDT, Jan 25 '13 at 06:34
@CDT: How many points are there? It is possible to guess the expected complexity from it. — nhahtdh, Jan 25 '13 at 06:36
You could speed up your algorithm by proper `for` ranges: `i` is okay, `j` should be `i+1..n`, `k` should be `j+1..n`. — Amadan, Jan 25 '13 at 06:37
a little bit different but maybe this question helps you http://stackoverflow.com/questions/10932958/find-a-line-passing-the-maximum-number-of-points — ibrahim, Jan 25 '13 at 06:39
@Amadan: It will still be O(n^3), though. Assuming the problem setter is good enough, it will still time out. — nhahtdh, Jan 25 '13 at 06:39
@nhahtdh: I am aware. It's still a better O(n^3); and it points out a problem in code as posted. I was not offering a better solution (for which I'd've created an answer), just fixing OP's. — Amadan, Jan 25 '13 at 06:40
@ibrahim: This is the good one to close this question as dup: http://stackoverflow.com/questions/4179581/what-is-the-most-efficient-algorithm-to-find-a-straight-line-that-goes-through-m — nhahtdh, Jan 25 '13 at 06:40

score 3 · Accepted Answer · answered Jan 25 '13 at 06:32

3

iterate each point, calculate the polar angle for each other point, sort the polar angle

this cost O(n^2*lgn)

answered Jan 25 '13 at 06:32

songlj

for polar angle calculation you should use `center`(normalization) coordinates. What coordinates the OP should use? – Dmitry Zagorulkin Jan 25 '13 at 06:40
the center should be the iterated point in the outter most "for loop" – songlj Jan 25 '13 at 06:42
@Amadan http://stackoverflow.com/questions/2676719/calculating-the-angle-between-the-line-defined-by-two-points – Dmitry Zagorulkin Jan 25 '13 at 06:44
Thanks a lot! This should get over the time limit~ – CDT Jan 25 '13 at 06:47
@songlj Why sort the polar angles? Can't we loop through the list and check the count of the most frequent angle? Giving cost O(n^2) – kgf3JfUtW Feb 27 '17 at 16:58

score 0 · Answer 2 · answered Jan 25 '13 at 12:25

I have not implemented this, but you might be able to do it in O(n).

Use a hashmap to store the points by their polar angles: Map<Double,List<Point>>, where Double is the angle
Then iterate the map, tracking the List<Point> with the max length. That list would contain the result.

Play with that. It looks like it should work.

2 Answers2