Find all collinear points in a given set

Question

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 ?

Answer 1

Collinear here doesn't really make sense unless you fix on 2 points to begin with. So to say, "find all collinear points in a given set" doesn't make much sense in my opinion, unless you fix on 2 points and test the others to see if they're collinear.

Maybe a better question is, what is the maximum number of collinear points in the given set? In that case, you could fix on 2 points (just use 2 loops), then loop over the other points and check that the slope matches between the fixed points and the other points. You could use something like this for that check, assuming the coordinates are integer (you could change parameter types to double otherwise).

// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Returns whether 3 points are collinear
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool collinear(int x1, int y1, int x2, int y2, int x3, int y3) {
  return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}

So the logic becomes:

int best = 2;
for (int i = 0; i < number of points; ++i) {
  for (int j = i+1, j < number of points; j++) {
    int count = 2;
    for (int k = 0; i < number of points; ++k) {
      if (k==i || k==j)
        continue;

      check that points i, j and k are collinear (use function above), if so, increment count.
    }
    best = max(best,count); 
  }
}

Answer 2

solve the problem in dual plane, convert all the points in to line segments. And then run a plane sweep to report all the intersections. The lines in the dual plane will pass through same point represents collinear points. And the plane sweep can be done in O(nlogn) time.

Answer 3

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.