如何有效地从给定点找到最远的点（从一组点）？
How to find the farthest point (from a set of points) from a given point efficiently?
我正在寻找一种算法或数据结构来解决以下问题：
给定一组点 S。
并且您将以另一点的形式获得 Q 查询。
对于每个查询，找到集合中距给定点最远的点。
集合中最多有10^5个点和10^5个查询。所有点的坐标都在 0 到 10^5 的范围内。
我想知道是否有一种方法可以存储点集，以便我们可以在必要时在 O(log n) 或 O(log^2 n) 中回答查询。
引自“Approximate Furthest Neighbor with Application
到环形查询":
In two dimensions the furthest neighbor problem
can be solved in linear space and logarithmic query time using point location in
a furthest point Voronoi diagram (see, for example, de Berg et al. [5]).
其中 [5] 指的是 "Marks textbook":
Berg, Mark de, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational geometry: algorithms and applications. Springer-Verlag TELOS, 2008.
一组八个点的最远邻 Voronoi 图。
图片来自 Jacometti, Welson。 "A Note on Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams." (1992)。
我正在寻找一种算法或数据结构来解决以下问题： 给定一组点 S。 并且您将以另一点的形式获得 Q 查询。 对于每个查询，找到集合中距给定点最远的点。
集合中最多有10^5个点和10^5个查询。所有点的坐标都在 0 到 10^5 的范围内。
我想知道是否有一种方法可以存储点集，以便我们可以在必要时在 O(log n) 或 O(log^2 n) 中回答查询。
引自“Approximate Furthest Neighbor with Application 到环形查询":
In two dimensions the furthest neighbor problem can be solved in linear space and logarithmic query time using point location in a furthest point Voronoi diagram (see, for example, de Berg et al. [5]).
其中 [5] 指的是 "Marks textbook":
Berg, Mark de, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational geometry: algorithms and applications. Springer-Verlag TELOS, 2008.
一组八个点的最远邻 Voronoi 图。
图片来自 Jacometti, Welson。 "A Note on Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams." (1992)。