计算每个点的最远点

Question

假设我们在平面上有两组点，比如 A 和 B（大小都为 O(n)）。我们能否在 O(n) 时间内找到位于 A 和 B 中的最远点对？

Answer 1

不可以，您无法计算O(n)中每个点的最远点。您可以获得的最好的是 O(n log n) 和 2-d tree。您可以使用类似于寻找最近点的技术来做到这一点。

阅读更详细的 ，其中我展示了解决类似问题的其他几种方法。