I recently was asked to come up with an algorithm to find all the lines for the given set of points that have more than two points on them. For instance if I have:
[(0, 0), (1, 1), (0, 2), (1, 2), (2, 2)]
I need to find all the lines that I can create with these points that includes at least three of them.
I started by finding all the pair combination of points, which is 10 different combinations. Then iterate through each pair, find the slope and y-intercept and then check the remaining points to see if they fit the equation. Or in case of slope = inf, I would just check the X value.
Just wanna know if this, brute force, is the only way or is there any other magic I could use in terms of efficiency.
The most efficient in terms of short coding is as follows. Constitute this large array:
$$\begin{bmatrix}x_1&x_2&\cdots &x_n\\y_1&y_2&\cdots &y_n\\1&1&\cdots &1\end{bmatrix}$$
and compute all the determinants of all $3 \times 3$ submatrices: those with a zero determinant correspond to aligned points.
This is due to the fact (signaled by @semiclassical) that the determinant
$$\begin{vmatrix}x_i&x_j&x_k\\y_i&y_j&y_k\\1&1&1\end{vmatrix}$$
is twice the area of triangle $M_iM_jM_k$, thus null if and only if the triangle is flat, i.e., iff its vertices are aligned.
Remark: It is evidently an $O(n^3)$ algorithm...
(3 nested loops : for $i=1 \cdots (n-2)$, for $j=(i+1) \cdots (n-1)$, for $k=(j+1) \cdots n$).