有谁知道解决以下问题的有效算法：
给定某个度量空间的两个不相交的点集 A、B，在 A 中找到一个点，它与 B 中最近点的最小距离最大？
问问题
225 次
3 回答
1
这是最近邻搜索的变体；如果您使用 kd 树来索引 B，那么通过 A 的蛮力搜索将具有 n * log(m) 的平均运行时间，其中 n 是 A 中的点数，m 是 B 中的点数。如果您将点聚集在 A 中并测试集群的质心，那么您应该能够通过一次查询消除多个点。
于 2013-05-01T23:22:54.910 回答
0
我不知道特定的算法。鉴于这个问题，我会开始尝试看看二进制印章是否可以完成这项工作。
但是，要取得进展需要更多信息：您说“点 A .. from B”就好像 B 是一个点，但 B 是一组点 - 实际上从问题定义来看，A 和 B 可能是同一组点，或至少重叠..
在尝试找到解决方案时，递归也可以提供帮助。也就是说，在给定 f(n-1) 的解的情况下找到 f(n) 的解。根据定义，如果 A 为 1 分，B 也是，则有 1 个已知答案。
然后你能概括 n = 2 的解决方案吗
例如，求解如果 A 为 2 分，B 为 1 分。其中A离B更远。
一旦你有一个 B 为 1 点的解决方案，你就可以推断出 B = a set 的解决方案。
高温高压
于 2013-05-01T22:42:42.047 回答
0
我怀疑给定一个度量 f，您可以使用 1/f 作为度量，然后进行简单的最近邻搜索。我唯一的问题是 1/f 是否满足三角不等式。
于 2013-05-01T23:36:07.727 回答