Author |
Topic: Collinearity Problem (Read 1519 times) |
|
grrarrgh1
Newbie
Posts: 2
|
 |
Collinearity Problem
« on: Dec 18th, 2003, 3:05pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender: 
Posts: 767
|
|
Re: Collinearity Problem
« Reply #1 on: Dec 18th, 2003, 11:46pm » |
Quote Modify
|
:: 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. ::
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  ).
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Collinearity Problem
« Reply #2 on: Dec 19th, 2003, 1:19am » |
Quote Modify
|
::create lines between all points ( O(n2) ). 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 (n2 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 (n2 log n) ::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
grrarrgh1
Newbie
Posts: 2
|
|
Re: Collinearity Problem
« Reply #3 on: Dec 19th, 2003, 1:42am » |
Quote Modify
|
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 n3 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
|
|
IP Logged |
|
|
|
NoNamePlease
Guest
|
on Dec 19th, 2003, 1:42am, grrarrgh1 wrote:| is not the normalization process order n, and therefore, multiplied by the n^2 lines to be normalized, bring about an order n3 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:
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
|
|
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)...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Collinearity Problem
« Reply #5 on: Dec 20th, 2003, 10:54am » |
Quote Modify
|
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..)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Collinearity Problem
« Reply #6 on: Dec 22nd, 2003, 2:04am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Collinearity Problem
« Reply #7 on: Dec 22nd, 2003, 4:01am » |
Quote Modify
|
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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove