algorithm - 给定两个点集 A 和 B，如何找到 A 中离 B 最远的点？

Question

有谁知道解决以下问题的有效算法:

给定某个度量空间的两个不相交的点集 A、B，找到 A 中的一个点，使到 B 中最近点的最小距离最大？

Answer 1

这是最近邻搜索的一个变体；如果您使用 k-d 树对 B 进行索引，那么通过 A 进行暴力搜索的平均运行时间为 n * log(m)，其中 n 是 A 中的点数，m 是 B 中的点数。如果您将点聚类在 A 中并测试聚类的质心，然后您应该能够通过一次查询消除多个点。