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

One of interesting solution for this problem is here.

Time complexity is O(n2)

Space Complexity- O(n)

https://stackoverflow.com/a/50207802/7438973

Answer 2

Take a look at the two methods described in http://www.cs.princeton.edu/courses/archive/spring03/cs226/assignments/lines.html .

To find 4 or more collinear points given N points, the brute-force method has a time complexity of O(N^4), but a better method does it in O(N^2 log N).