我正在开发一个模拟程序。程序中包含多个动物（角马）群体，我需要能够快速找出其中一只远离兽群的动物。
在下面的图片中，绿色点表示远离兽群的动物。我希望能够快速找到这些点。
当然，有一种简单的算法可以解决这个问题。计算每个点周围邻域中的点数，如果该邻域内没有点（即0个点），那么我们就知道这个点是远离兽群的。
问题是这种算法效率极低。我有一百万个点，对每百万个点应用这个算法会非常慢。
有没有更快的方法？也许可以使用树结构？
编辑给@amit：我们希望避免这种情况。左下角的一组绿色点会被选中，尽管它们不应该被选中，因为这不是一只远离兽群的动物，而是一群动物。我们只寻找一只远离兽群的动物（不是一群）。
回答：
对于最近邻查询，通常使用kd树。这将导致O(n log n)的查询时间（一次查询是log(n)乘以n次查询，构建kd树本身也是O(n log n)），我认为这对于几百万个点来说运行速度会非常快，而且已经有一些非常高效的库可用（例如ANN）。
此外，ANN代表“近似最近邻”，当不需要精确距离时，它可以更快。由于在你的情况下，你只需要检测第一个最近邻距离是大还是小，你可以设置一个相当高的阈值，这将使事情变得更快。
从中，你可以确定每个人最近邻的距离分布，并找出异常值。排序所有这些距离以确定异常值再次是O(n log n)。
