Alex Rivera | Logout

Find all collinear points in a given set

Asked 2010-12-29T21:04:54.153
14

This is an interview question: "Find all collinear points in a given set".

As I understand, they ask to print out the points, which lie in the same line (and every two points are always collinear). I would suggest the following.

  1. Let's introduce two types Line (pair of doubles) and Point (pair of integers).
  2. Create a multimap : HashMap<Line, List<Point>)
  3. Loop over all pairs of points and for each pair: calculate the Line connecting the points and add the line with those points to the multimap.

Finally, the multimap contains the lines as the keys and a list collinear points for each line as its value.

The complexity is O(N^2). Does it make sense ? Are there better solutions ?

algorithm geometry
Edit
Report

1 Answer

0

Are you sure your analysis of the runtime is correct? You say to loop over all the pairs of points, of which there are n*(n-1)/2, i.e. O(n^2). Then you add the line and the pair of points to the map. However, I don't think the time to add such a line + point combination is constant. This means overall your time is O(n^2 log n) not a constant times n^2, which is what O(n^2) means.

So the real question would be, given that it can be done in time O(n^2 log n) can it be done in time O(n^2). Clearly O(n^2) gives a lower bound as you must at the very least print out every pair of points, of which there are O(n^2). My feeling is this is a completely general sorting problem and that one cannot expect better than O(n^2 log n) in general. However a full proof of that fact may be non-trivial.

Another thing to beware of is that the set may contain zero or one points, and so you will need to check that your algorithm handles these cases correctly, otherwise write special cases for those.

answered 2011-01-07T14:19:09.307

Your Answer