algorithm - 计算社区（互连节点）到另一点之间距离的高效算法

Question

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

这里一个合适的距离函数可以是平均所有点到查询点的距离。另一种功能可能是取所有距离中的最大值。

我该如何解决这个问题？

Answer 1

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