# Finding approximately collinear points

my issue comes from image processing. The image below is for a better understanding of the problem. I have to detect three dots (shown in black, marked with red arrows). The other points I get from my image after processing it are shown in green. As you can see I get many more points from the image than just the black ones, due to other structures inside the picture. So I've got a set of points and I know that there are at least three of them that are on a curve which is approximately a line and the approximate distance between the points is also known. I need to find these three points from my set.

The algorithm should be able to detect whether there is such a structure in the picture or there isn't one.

A simple algorithm is to iterate over all ways to choose 3 of the points, and test whether those 3 satisfy your criteria (are approximately colinear, have the appropriate distances, etc.). There are ${n \choose 3}$ such triples, so the running time of this algorithm is $O(n^3)$.

It is possible to improve on that. Here is an algorithm whose running time is $O(n^2 \log n)$:

• For each point $p$:

• Sort the points by their slope to $p$. In other words, for each point $q$, calculate the slope of the line connecting $p$ and $q$, and use this as the key to help you sort the points.

• Look for two points $q_1,q_2$ such that the slope of the line connecting $p$ and $q_1$ is approximately the negative of the slope of the line connecting $p$ and $q_2$. You can check whether such a pair of points $q_1,q_2$ exist by a linear scan over the sorted list built in the previous step. For each such pair, test whether $q_1,p,q_2$ satisfy your criteria (are approximately colinear, have the appropriate distances, etc.); if they are, output them.

The running time is $O(n^2 \log n)$, since for each iteration of the outer loop you do $O(n \log n)$ work, and the outer loop does $n$ iterations.

The above algorithm sorts the list of points by their slope, to make it easier to find 3 points that are approximately colinear. You could also sort the list of points by their distance to $p$, to make it easier to find 3 points at the prescribed distances. It's hard to say a priori which one might work better, but you could certainly try them both.