給定兩個點集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

回答