Line up problem ..

helloneo · Post by **helloneo** » Tue Jul 25, 2006 5:31 am

There are many points in x, y coordinates and I'd like to get a straight line which contains as many points as possible..
I only have O(n^3) solution.. Is there any more efficient way..?
Thanks..

mf · Post by mf » Tue Jul 25, 2006 7:24 am

O(n^2 log n) is possible (and even expected O(n^2) with hashtables.)
Read topics on this board on problem 270.

misof · Post by **misof** » Wed Jul 26, 2006 12:49 pm

I think that you can get to worst-case O(N^2) using point-line duality. Transform the problem into "given N different lines, find the largest subset that pass through the same point", and then traverse the whole plane subdivision given by the N lines, and look for a vertex with the largest degree.

Of course, this is just a theoretical result, not what I'd (want to) implement. mf's suggestions are way easier to implement.

helloneo · Post by **helloneo** » Sun Jul 30, 2006 1:02 pm

Thanks..~ I finally figured that out ..

Cosmin.ro · Post by **Cosmin.ro** » Mon Jul 31, 2006 2:31 am

You can hash the n^2 intersection points in the dual plane, and get a easier O(n^2) solution but it's O(n^2) memory.

Popritfim · Post by **Popritfim** » Thu Aug 03, 2006 3:26 am

Achtung!!