techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Line question

In a plane, n points are given i.e. the input is (x1,y1), (x2,y2)... (xn,yn). Given these n points.Find the maximum number of collinear points.

Monday, December 24, 2007
 
 
If you want to find out max. no collinear points then that will be trivially C(n,2) since 2 points will be collinear.
So I modify the problem a bit..say find out the no of triples of points that collinear.
If you want to find out 3 points lying on a line then a trivial algo. would be to check for all possible triplets of points whether they are collinear. That takes O(n^3). Another method is to obtain dual of a problem and then the problem becomes finding out the no of intersection points which have degree more than 6 (at least 3 lines intersecting together in the dual plane). Since max. no of intersections in the dual plane is n^2, it becomes O(n^2).
dark horse
Monday, December 24, 2007
 
 
This question gets misunderstood every time it is asked.  A set of points is collinear if all of them lie on the *same* line.  He's not asking "how many sets of 3 points can you find where each set of 3 is collinear" but rather "what's the largest number of points that are all on the same line."
Kevin Send private email
Monday, December 24, 2007
 
 
Fine..still the duality algorithm would work. Find the point of intersection with maximum no of lines incident on it in the dual plane. It works in O(n^2). To be specific, we can maintain a data structure such as DCEL where we can store the edges incident on the point so that just counting them for each point will give us the maximum value.
dark horse
Monday, December 24, 2007
 
 
O(n^2) seems trivial.  I wonder if there's an O(n*log(n)) solution?
Skorj Send private email
Monday, December 24, 2007
 
 
Hmmm, I don't see how one could possibly beat O(N^2) since it seems you have to consider at least every pair of points. 

I think this is O(n^2):
* Create an object for each pair of points
* Sort by slope
* For each group with the same slope, find the lower-left point that occurs most frequently
* Find the max count above across all groups
Skorj Send private email
Monday, December 24, 2007
 
 
what is implied by
"  For each group with the same slope, find the lower-left point that occurs most frequently "

Isnt the number of points in the same group give us the count we are looking for ?

Tuesday, December 25, 2007
 
 
> Isnt the number of points in the same group give us the count we are looking for ?

Lines with the same slope aren't necessarily collinear. Probably Skorj means to find, say, the y-intercept that occurs most frequently.
andy
Tuesday, December 25, 2007
 
 
Points in the same group are not necessarily collinear.  However, if the points { A, B, C, D } are collinear from lower left to upper right, the following pairs will appear when sorted by lower-left point.

    A-B, A-C, A-D, B-C, B-D, C-D

A has the highest count.  A-B, A-C, and A-D have the same slope and contain a common point, so therefore A-B-C-D are collinear and this is the largest colliner set.
Skorj Send private email
Thursday, December 27, 2007
 
 
Isn't Skorj's algorithm O(n^2 log(n)) since you have to sort n^2 things?

Sunday, December 30, 2007
 
 
log(n^2) = 2*log(n)
O(log(n^2)) = O(log(n))
Skorj Send private email
Monday, December 31, 2007
 
 
My point is that if you are using an O(N log(N)) algorithm to sort N=n^2 things, then it takes O(n^2 log(n^2))=O(n^2 log(n)) time, not O(n^2).

Monday, December 31, 2007
 
 
Here's O(n^2):
- Allocate a chained hash table of size n^2. Each slot stores a list of points and the length of that list.
- Start maximum_length at 0
- Keep a pointer to the hash element with the maximum length.
- For each pair of points:
- - calculate the slope and y-intercept as rational numbers
- - use that as a key and insert the two points into the list at that key in the hash
- - increment the length
- - and update maximum_length and the pointer if necessary
- The maximum length list has duplicate points, remove them.

Hash table accesses are O(1). Traversing each pair is O(n^2). Removing duplicates costs at most O(n^2) if you allocate an n^2 array, insert the items, and then traverse it.
Nat Send private email
Tuesday, January 01, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz