I am developing a simulation program. There are herds of animals (wildebeests), and in that herd, I need to be able to find one animal that is away from the herd.
On the picture below, green dots are away from the herd. It is these points that I'd like to be able to find quickly.
Of course, there is a simple algorithm to solve that problem. Count the number of dots in the neighborhood of each point, and then if that neighborhood is empty (0 point in it), then we know that this point is away from the herd.
The problem is that this algorithm is not efficient at all. I have one million points, and applying this algorithm on each of the million points is very slow.
Is there something that would be faster? Maybe using trees?
We want to avoid that case. A group of green dots in the left corner would be chosen, even though they should not because it's not a single animal that is away from the herd, it's a group of animals. We are only looking for one single animal away from herd.