找到一個點，使距離一個有限區域內的一組點的總距離最大

Question

給定一組點p，我想找到空間b內的一個點，該點限定儘可能遠的區域p來自p內的所有點。

這是關於在植絨模擬中按照Craig Reynolds' Boids實施鄰居避免 - 如果這不是避免鄰居的最佳方法，我會喜歡建議。

編輯： 換句話說，我想找到一個任意點是遠離其他點p成爲可能，而周圍p邊框之內。

通過邊界框我的意思是溶液應具有一個點的Y座標爲上和最下點之間，和一個x座標是左側和最右側的點之間。

提出這個問題更抽象，我在看這個算法，以此來發現目標爲希望留內M單位其最近的鄰居，而不是越來越近了超過m他們單位的代理人。該算法返回的解決方案應返回距離其最近鄰居點最遠的點。

這是在2D平面。

Answer 1

聽起來好像該溶液必須位於的（其他）劑維諾圖的交叉點中的一個。因此，算法解決方案是構建Voronoi圖，迭代交叉點，並選擇距離鄰居最近的距離。

Answer 2

我覺得最遠點應該是在包裝盒上邊界或在其兩個最接近點之間的距離相等。如果不是這樣，那麼你應該能夠稍微調整一下，使它離兩點中較近的點更遠。這將它放在圖表的一行上。沿着這條線的一個方向會使它從兩個點進一步移動，所以你可以移動它直到該線在某一點連接另一個點。因此，我認爲它不是在邊界上，就是在http://en.wikipedia.org/wiki/Voronoi_diagram的一個交叉點上。您可以檢查邊界的角點，Voronoi圖的線與邊界相交，Voronoi圖的交點用於找到最遠點。即使你不這樣做，你可能會發現Voronoi圖有用作爲尋找最近鄰居的方法來尋找另一種方法 - 某種分支和邊界可能會起作用。