数据结构-计算社区(互连节点)到另一点之间距离的有效算法

Question

我在空间域中有一个图结构（比如说密集的类似社区的结构）和一个查询点。我想设计有效的算法+数据结构来计算整个组与查询点之间的距离。

这里合适的距离函数可以是对所有点距查询点的距离进行平均。一个替代函数可以取所有距离中的最大值。

我该如何解决这个问题？

Answer 1

如果空间距离：我建议使用均方根距离，与质心不同，这符合您两个建议的精神，因为它是从查询点到社区中每个点的距离的函数。通过对变量x和y中的每个点（x，y）的距离平方多项式（x-x）^2+（y-y）^2求和来预处理社区。然后通过插入查询点，除以社区点的数量，并取平方根来计算RMS距离。