## Line up problem ..

Let's talk about algorithms!

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Line up problem ..

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
O(n^2 log n) is possible (and even expected O(n^2) with hashtables.)
Read topics on this board on problem 270.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Thanks..~ I finally figured that out ..

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 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
New poster
Posts: 1
Joined: Thu Aug 03, 2006 3:06 am
Location: USA
Contact:
Achtung!!