1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.