这个问题提出了几个问题。赏金将去哪个整体解决他们一个答案。

This question raises several issues. The bounty will go to an answer which addresses them holistically.

这里有一个问题，我一直在玩。

Here's a problem I've been playing with.

注意我正在不是基于欧几里德空间的解决方案非常感兴趣。

有一组参与者形成一个人群大小K的距离 D的（ActorA，ActorB）是易于计算的任何两个角色（解决方案应该工作距离）和各种定义，我们可以找到这一集N个最近邻用于使用任何数量的既定算法任何给定的演员。

There is a set of Actors which form a crowd of size K. The distance d(ActorA,ActorB) is easily computable for any two actors (solutions should work for various definitions of 'distance') and we can find the set of N nearest neighbours for any given Actor using any of a number of established algorithms.

这邻居集是在第一瞬间正确的，但的演员一直在移动，我想保持N个最近的邻居每个演员不断变化的列表。我所感兴趣的是近似的解决方案，这是完美的解决方案更有效。

This neighbour set is correct at the first instant but the Actors are always moving and I want to maintain the evolving list of N nearest neighbours for each Actor. What I am interested in is approximate solutions which are more efficient than perfect solutions.

解决方案应该收敛到正确已被引入错误后。 这是可以接受的，有时执行完整的重新计算，如果误差过大，但检测这些错误应该是便宜 Solutions should converge to correctness after errors have been introduced. It is acceptable to sometimes perform a full recomputation if the errors become too large but detecting these errors should be cheap.

到目前为止，我一直在使用的的朋友的一朋友的算法：

So far I have been using a friend-of-a-friend algorithm:

recompute_nearest (Actor A)
{
    Actor f_o_f [N*N];
    for each Actor n in A.neighbours
        append n to f_o_f if n != A and n not in f_o_f

    Distance distances [N*N];
    for 0 <= i < f_o_f.size
        distances [i] = distance (A, f_o_f [i])

    sort (f_o_f, distances)
    A .neighbours = first N from f_o_f
}

这表现相当不错，当人群中缓慢移动，N是适当大。它收敛后误差小，满足了第一个条件，但

This performs reasonably well when the crowd is slow-moving and N is suitably large. It converges after small errors, satisfying the first criteria, but

在我没有发现大的错误的好办法， 予有误差的大小和频率没有定量描述， 在其收敛的做法，但我不能的证明的，它总是会。 I don't have good way to detect large errors, I have no quantitative description of the size and frequency of errors, it converges in practice but I can't prove that it always will.

您可以帮助任何这些问题的？

Can you help with any of these points?

另外，你知道哪个表现好任何替代方法

Also, do you know of any alternative approaches which perform well

在人群中快速移动， 在当前的部分的演员都是快速移动， 当N很小， 当人群稀疏，有些地方和密集的人， 或特定空间索引算法？ when the crowd is fast-moving, when some actors are fast-moving, when N is small, when the crowd is sparse in some places and dense in others, or with particular spacial-indexing algorithms?

我的工作，此刻的延伸，是推广的朋友的一朋友拿。我怀疑这不能扩展到好，这是很难得出正确的参数没有错误的定量。

The extension I'm working on at the moment is to generalise friend-of-a-friend to take the friend-of-a-friend-of-a-friend in cases when a neighbour is fast-moving. I suspect that this doesn't scale to well and it's hard to derive the right parameters without a quantification of the errors.

我欢迎所有的建议！这是一个有趣的小问题： - ）

I welcome all suggestions! It's a fun little problem :-)

Fexvez：样本随机额外的邻居，样本大小取决于代理的速度。 从它要进入很可能也有利于该地区采样。的

Fexvez: sample random extra neighbours, sample size depending on the speed of the Agent. Sampling from the area it's about to move into would probably also help.

重采样邻居当代理速度* delta_time 超到最远已知的邻居的距离。

Resample the neighbours when an agents speed*delta_time exceeds the distance to the furthest known neighbour.

保持 Delaunay三角的是最近邻图形的超集。 只占一个近邻。的

Maintain the Delaunay triangulation which is a superset of the nearest-neighbour graph. Only accounts for one nearest neighbour.

大卫摩的安库的似乎没有处理< STRONG>移动的身体。的

David Mount's ANN library Doesn't seem to handle moving bodies.

推荐答案

从统计很简单，很快速的方法是使用随机线性预测。这些可以帮助您确定集群和邻居非常快。随着越来越多的预测，你会得到更准确（涉及您的有关错误的问题，我相信）。

A very simple and very fast method from statistics is to use random linear projections. These can help you determine clusters and neighbors very quickly. With more projections, you get more accuracy (addressing your question about errors, I believe).

本文的提供的几种方法，包括一个新的方法，广泛的定量分析（DPES ），其相关的RLP

This paper offers an extensive quantitative analysis of several methods, including a new method (DPES) that is related to RLP.

本文地址使用RLP，包括远距离preservation即使在的范围内移动点的。

This paper addresses use of RLP including for distance preservation even in the context of moving points.

本文解决RLP的运动规划，并详细介绍一些启发。

This paper addresses RLP for motion planning and details several heuristics.

RLP方法是：

非常快 铅，以近似的可调谐的精度和速度 在距离和角度preserving（可证明的） 很容易地扩展到大尺寸和物体的大＃分别 有用的降维 铅紧凑的预测（例如，一个可以投射到一个层次二元分割） 灵活：可以投射到任何空间，你觉得会是对你有好处 - 通常R 2万桶，但伸入2 ^ D（尺寸D即二进制空间）也是允许的，仅须在精确度下降一个给定的＃的预测。 统计有意思

嵌入到较低维空间中之后，邻居的计算是非常容易的，因为凸起被，比方说，分级中的相同区域（如果bin中的突起成网格）很可能接近在原始空间。

After embedding into a lower dimensional space, neighbor calculations are very easy, as projections that are, say, binned in the same regions (if you bin the projections into a grid) are very likely to be close in the original space.

尽管原始数据的维数是小的（甚至是10小），能够迅速伸入一个$ P $对选定的网格的能力是用于识别和计数邻居非常有用的。

Although the dimensionality of the original data is small (even 10 is small), the ability to rapidly project into a pre-selected grid is very useful for identifying and counting neighbors.

最后，你只需要更新的那些对象的位置（或相对位置，如果你中心和缩放数据）已经改变。

Finally, you only need to update for those objects whose location (or relative location, if you're centering and scaling the data) have changed.

有关相关的工作，可查看到约翰逊Lindenstrauss引理。

For related works, look into the Johnson-Lindenstrauss lemma.