wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Collinearity Problem
        
(Message started by: grrarrgh1 on Dec 18^th, 2003, 3:05pm)

Title: Collinearity Problem
Post by grrarrgh1 on Dec 18^th, 2003, 3:05pm

From a newbie; sorry if this is posted inelegantly, or under/overstates the in/obvious:

Say you have n points in 3-space, and you want to figure out the largest number of points on any line that can be drawn -- what is the most efficient worst case solution from a computing perspective?

My instinctive response (ignoring issues of truncation and so on), is to say, something on the order of n^3 -- which is the order that results from having to test each set of three points in the worst case of there being no three points on the same line.

Is there a better solution method for the worst case, and if so, what is it? In case this is a well-known (solved) computing problem, please de-highlight the solution, as I'd like to think about it some more.

Of course, if you are certain that there is no more elegant solution, please post that as well.

thanks

Title: Re: Collinearity Problem
Post by John_Gaughan on Dec 18^th, 2003, 11:46pm

:: [hide]A line is determined by two points. In the worst case, you would take the first point (n), combine it with each of the others (n-1) to get all lines, then test the line for colinearilty against all the other points (n-2). Each time you finish calculating a line, record how many points lie on it (constant). So yes, n[sup3] sounds about right.[/hide] ::

There is something that is nagging me about that explanation, something about removing duplicate lines... but it is almost 2 am, my brain needs sleep before it can contemplate more math :-)

Of course there are ways to make it more efficient, but I am a firm believer in getting code to work first, then making it work better later (after you hand the project off to another programmer ;-) ).

Title: Re: Collinearity Problem
Post by towr on Dec 19^th, 2003, 1:19am

::[hide]create lines between all points ( O(n²) ). Store the normalized direction vector and a starting vector that is perpendicular to the direction (and starting in the origin). This way every line has one unique representation, sort the array of lines ( O (n² log n) ), find out which line occurse most often, and if you've stored which points go with it (easy enough to do), you're done in O (n² log n) [/hide]::

Title: Re: Collinearity Problem
Post by grrarrgh1 on Dec 19^th, 2003, 1:42am

towr,

this may just be due to my casual (and hence, spotty) acquaintance with calculating order/CS, or a misunderstanding of what you propose, but is not the normalization process order n, and therefore, multiplied by the n^2 lines to be normalized, bring about an order n³ solution?

If I'm wrong, thank you for the improved solution (thank you either way, actually, for the effort) -- though I can't help thinking there is something even better...ah well...enough procrastination on puzzles...i'm actually on eastern time :)

Title: Re: Collinearity Problem
Post by NoNamePlease on Dec 19^th, 2003, 3:31pm

on 12/19/03 at 01:42:44, grrarrgh1 wrote:

is not the normalization process order n, and therefore, multiplied by the n^2 lines to be normalized, bring about an order n³ solution?

Towr's "normalization" is just a matter of representing a line in a standard form, so you don't need to iterate over all other lines. I had a variant of this:
[hide]
Code:

MaxPts := 2
For all points (i):
For all points (j), j != i:
D(i,j) := (x,y,z)_j - (x,y,z)_i
//This is like moving origin to point i
D(i,j) := D(i,j)/|D(i,j)|
//normalizing
EndFor
Sort(D(i))
//Next pick longest sequence of same values
//in D(i), say, L.
If L+1 > MaxPts
MaxPts = L+1
EndFor

[/hide]
This is slightly better than towr, since you don't need as much storage space and normalization process is easier.

There is one problem to consider: if all coords are integers, then normalization may give you an FP error that may screw up your "same values" selection.

Second, I cannot help thinking there may be a more elegant solution based on finding the rank of D(i,j)...

Title: Re: Collinearity Problem
Post by towr on Dec 20^th, 2003, 10:54am

your normalization may be simpler, but unless I'm mistaken you bunch together all line-pieces that are parallel, even if they're not on the same line.. (that's why I included a standardized point on each line, the one that lies closest to the origin)

And of course an obvious improvement would be to number all points and make lines between points i and points j>i (which cuts the number of lines to consider in half. It does nothing for the order though..)

Title: Re: Collinearity Problem
Post by Eigenray on Dec 22^nd, 2003, 2:04am

No, for each point i, he finds the maximum number of points j which which lie on a single line through i, in O(n log n). He then does this n times, storing the max over all i.

Title: Re: Collinearity Problem
Post by towr on Dec 22^nd, 2003, 4:01am

ah.. That's clever..

good thing I included an "unless I'm mistaken "-clause ;)

One thing we might do to make normalization simpler, is divide the direction vector by the z (or x or y) coordinate, instead of the length of the vector. Since we're only interested in making them appear the same when they are, and this will suffice, the length doesn't matter .
If they're integers we could divide by the greatest common divisor (though finding it takes some extra operations).