最近欧氏距离的高效数据结构

Question

该问题受到以下 UVa 问题的启发： https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628.

亚马逊地区已经安装了一个由电池供电的自主数据采集站网络来监测气候。订单调度站可以向控制站发送指令，以便控制站更改其当前参数。为了避免电池过载，每个站（包括订单调度站）只能向另外两个站传输。车站的目的地是最近的两个车站。在抽签的情况下，第一个标准是选择最西边（地图上最左边），第二个标准是选择最南边（地图上最低）。您受亚马逊州政府委托编写一个程序，根据每个站点的本地化情况，决定消息是否可以到达所有站点。

当然，简单的算法会构建一个以站点作为顶点的图，并通过搜索所有其他顶点来查找最近的两个顶点来计算给定顶点的边。然后，我们可以简单地运行DFS/BFS。当然，这需要 $O(V^2)$ 构建图表的时间（确实通过了测试用例）。不过，我的问题是，我们是否可以使用适当的数据结构更快地构建图表。具体来说，给定任意查询点 $p$ 和给定的一组点 $S$, ，我们可以组织一下中的点吗 $S$ 这样我们就可以快速找到两个最接近的点 $S$ 到 $p$ （比如说，在 $\logV$ 时间？）。

Answer 1

如果我理解正确的话，大多数空间索引都可以使用。

空间索引通常大约有 $O(日志{V})$ 插入时间和最近邻居的类似查找时间。当然，您可以从中创建一个 Voronoi 图，但您也可以在需要时直接使用索引来查找最近的邻居。

对于低维（2D、3D），空间索引的常见族是 kd树 （非常简单并且总体上很好，但是在密集的点簇上往往会出现问题）， 四叉树 （自己实现有点困难，因为数值精度可能很棘手）和 R树 （最难实现，但能提供最好的性能保证，尤其是 R*Tree（R-Star-Tree））。

如果您使用 C++，请查看 lib空间索引 或者 Boost R 树. 。如果您使用 Java，请查看我的 锡锡 图书馆。

其技术术语是“$k$ 最近邻查询”或“$k$-NN 查询”，其中 $k$ 指的是您要查找的最近邻居的数量。

Answer 2

似乎相关的数据结构可能是动态 voronoi图。

voronoi图通常是涉及飞机上一组点时的答案。

在这种情况下，由于点集是在发展的情况下，您想要动态版本。