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

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

2013-05-01 user695652

如果我们对度量空间没有更多了解，则不需要。 – 2013-05-01 22:34:52

这让我想起[图的直径]（http://mathworld.wolfram.com/GraphDiameter.html）（最小值的想法）。 – 2013-05-01 22:36:43

@David Eisenstat假设有一个距离oracle报告两个时间点O（1）之间的距离。 – user695652 2013-05-01 23:12:10

我不知道一个特定的算法。鉴于这个问题，我会开始尝试查看二元印章是否可以完成这项工作。

为了取得进展，需要更多的信息：你说“从B点A ..”就好像B是一个点，但B是一组点 - 事实上从问题定义A和B可能是相同的一组点或至少重叠..

在试图找到解决方案，递归也可以是一个帮助。也就是说，给出f（n-1）的一个解，找到f（n）的一个解。根据定义，如果A是1分，B也是，那么有1个已知的答案。

你能然后概括对于n = 2

例如溶液，解决如果A是2点，B是一个点。其中A距离B更远。

一旦您有一个解决方案，其中B是1分，那么您可能能够推导B =一组的解。

HTH

2013-05-01 22:42:42 rivimey

这是最近邻搜索的变体;如果使用kd树来索引B，那么通过A的穷举搜索将具有n * log（m）的平均运行时间，其中n是A中的点数，m是B中的点数。如果您将您的点集中在A中并测试群集的质心，那么您应该能够通过一个查询消除多个点。

2013-05-01 23:22:54

我怀疑给定度量f，你可以用1/f作为度量，然后做一个直接的最近邻居搜索。我唯一得到的是1/f是否满足三角不等式。

2013-05-01 23:36:07 Joel

回答