Here's a simple idea. (clustering approach)
Put your animals in a grid based on their x,y values.
If you don't want false detected outliers you could use two grids.
In this example I use two grid containers illustrated with black and a blue lines.
An outlier is defined as: an animals which is alone in both it's blue and black grid.
You keep a reference between the grid index and the animal contained in the grid.
Iterate the animals and put them in the grids using their x,y values.
Then iterate the black grids. When the grid content is 1 then find the blue grid reference through the animal which is inside the black grid. Check the content of the blue grid. If it is 1 then the animal is an outlier.
The running time should be pretty fast.
n: number of animals
b: size of black grid
Put the animals in the grids is O(n)
. Iterating the black grid is O(b)
This gives O(n) + O(b)
in total for building information and locating outliers.
Locating the outliers take O(b)
time. If your grid is small enough this will ensure a very fast running time.
The image above should illustrate two outliers.
The implementation should be relatively simple. You can play with variants of grid based strategies, use different layout of the grid or use more grid containers.
Edit:
This approach is somewhat related to the cell method described in this paper without distance calculation. http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-r-186.pdf
This method will not exclude false detected outliers for all cases. For more perfect solution (for all possible positions of animals on the map) you will have to add distance calculation from detected 1 animal in a cell to neighbor cell content. You can read more about it here.