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

集合中最多有10 ^ 5个点,而查询则有10 ^ 5个。点的所有坐标都在0到10 ^ 5的范围内。

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

最佳答案

引用“最远的邻居与应用程序”
到环形查询”:



其中[5]指的是“商标教科书”:



algorithm - 如何有效地找到给定点的最远点(从一组点中)?-LMLPHP

一组最远的邻点Voronoi图。

图片来自Wecom的Jacometti。 “关于操纵一般分割和计算Voronoi图的原语的注释。” (1992)。

关于algorithm - 如何有效地找到给定点的最远点(从一组点中)?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/54153637/

10-09 06:15