如何有效地从给定点找到最远点(从一组点)？

Question

我正在寻找一种算法或数据结构来解决以下问题:给你一组点S.你会得到另一个点的Q查询.对于每个查询,从给定点找到集合中的最远点.

集合中最多有10 ^ 5个点和10 ^ 5个查询.点的所有坐标都在0到10 ^ 5之间.

我想知道是否存在一种存储点集的方法,以便我们可以在必要时回答O(log n)或O(log ^ 2 n)中的查询.

Answer 1

引用《近似最远邻居及其环空查询应用》：

在二维中，最远邻居问题可以使用最远点 Voronoi 图中的点位置在线性空间和对数查询时间中解决（例如，参见 de Berg 等人 [5]）。

其中[5]指的是“Marks教科书”：

Berg、Mark de、Otfried Cheong、Marc van Kreveld 和 Mark Overmars。计算几何：算法和应用。施普林格出版社 TELOS，2008 年。

         
          ^{一组八个点的最邻近 Voronoi 图。
图片来自 Jacometti、Welson。“关于一般细分操作和 Voronoi 图计算的原语的注释。” （1992）。}