# Given a set of points, find all collinear subsets

### General problem

• Given a space $S$ which is $N$-dimensional, bounded, and quantized
• Given a set $P$ of unique points
• Find the set of collinear subsets of $P$, each containing at least 3 points
• One point can exist in multiple subsets

### Specific problem

I am creating a 4D, 5 by 5 by 5 by 5 tic tac toe game. Each dimension is bounded by $\left(0,4\right)$ and quantized by $1$. I have a set of points within that space. Each point is associated with a player (the number of players is not bounded), so that could be treated as an additional bounded, quantized dimension.

I need to find any and all combinations of 5 points (played by the same player) that are collinear.

### Question

What is an efficient way to do this?

Here is a simple algorithm. For each way to choose 2 points from $P$, find the line that goes through those two points and then find all other points from $P$ that are on the line. If this yields at least 3 points, output it. Continue until you've iterated over all possible ways to choose 2 different points rom $P$.
The running time will be at most cubic. In particular, suppose there are $m$ points in the set $P$. Then there are ${m \choose 2} = m(m-1)/2$ ways to choose two different points from $P$. Thus, you'll do $\Theta(m^2)$ iterations. Then you can find all other points on the line in at most $O(m)$ time, so the total running time is $O(m^3)$.
There are probably more efficient algorithms. However, this might probably suffice for your needs. Specifically, in your example, you'll have $m \le 5^4$. Also, each iteration can be done faster than $O(m)$ time: given two points $p,q \in P$, you only have to check at most 3 other cells in the tic-tac-toe space. So, in your situation, the running time is $\Theta(m^2)$, and $m^2 \approx 2^{18.6}$, so this should be pretty fast.
• @BenKoshy, I suggest asking a new question with the specifics of your situation and the parameters, as the best algorithm might depend on the specifics of the space $S$.