algorithm - 寻找有限集中到另一点最近点的有效算法

Question

我有一个包含约 30k 个位置的列表 L(写为经度/纬度对)，以及一个包含约 1m 个事件的列表 E(包含写为经度/纬度对的位置)，每个事件都发生在 L 中的一个点。我想用 L 中对应的位置标记 E 中的每个事件。但是 L 和 E 中的坐标四舍五入不同——E 到小数点后五位，L 到十三位——所以表面上相同的坐标实际上可能相差 ~10^-5 度, 或 ~1 米。 (L 中的点至少间隔 ~10 m。)

因此，我需要 L 中与 E 中每个点最近的点；明显的 O(|L||E|) 蛮力算法太慢了。与 E 相比，L 足够小，因此预处理 L 并将预处理时间分摊到 E 上的算法很好。这是一个经过充分研究的问题吗？我能找到的链接是针对相关但不同的问题，例如找到一组中一对点之间的最小距离。

可能相关:Voronoi diagrams ，尽管我看不出将 L 预处理成 Voronoi 图会如何节省我的计算时间。

Answer 1

是的，你是对的。首先，您可以使用 Furtune's Sweep Line 在 O(|L| log |L|) 时间内构建位置点集 L 的 Voronoi 图。方法。可以使用各种实现，Triangle将是最常见的。

现在你有了一个 O(|L|) 大小的平面分割。要允许 O(log |L|) 最近邻查询，您需要在 Voronoi 图顶部有一个搜索结构。一种常见的方法是使用 Dobkin-Kirkpatrick 层次结构，详细信息可以在各种 lecture notes 中找到。 .此方法支持 O(log |L|) 查询，也只需要 O(|L|) 大小。 (也在 this post 中提到。)

然后 |E|查询可以在 O(|E| log |L|) 时间内完成。

另一种方法是使用 k-d trees .从实现的角度来看，它们可能工作更少，并且提供相同的复杂性(据我所知)。快速搜索显示这两个可能值得测试的实现:C++ , Java .