如何高效地从一组点中找到距离给定点最远的点？

Question

如何高效地从一组点中找到距离给定点最远的点？

algorithmdata-structurescomputational-geometryeuclidean-distance

9

我正在寻找一种算法或数据结构来解决以下问题：给定一个点集S。并且以另一个点的形式给出Q个查询。对于每个查询，请从给定点找到集合中最远的点。

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

我想知道是否有一种存储点集的方法，使我们可以在O(log n)或O(log^2 n)的时间复杂度内回答查询。

- Nikola Pesic

2

这个有帮助吗？https://codeforces.com/blog/entry/50466 - גלעד ברקן

欧几里得平面？ - David Eisenstat

此外，查询是在线的还是离线的？ - David Eisenstat

@גלעדברקן 三分查找的答案不起作用。最远点 Voronoi 是一个合理的答案，但我想知道如何在不写大量代码的情况下构建和执行图中的点定位。 - David Eisenstat

@DavidEisenstat 哎呀，如果你都不能给出答案，那还有谁能呢？:) 我还没有学习过最远点 Voronoi。我问这个链接是否有帮助是真诚的。 - גלעד ברקן

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joseph O'Rourke · Accepted Answer

来自“近似最远邻问题及其在环形查询中的应用”的一句引言：

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

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

Berg, Mark de, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational geometry: algorithms and applications. Springer-Verlag TELOS, 2008。

^{八个点的最远邻 Voronoi 图。

图片来源：Jacometti，Welson。《关于操纵一般细分和计算 Voronoi 图的基元的注释》（1992年）。}