合成一組二維點的算法

我有一組二維點/座標，我需要在所有點對之間考慮一定的最小距離。此外，每個點都與我想要維護的一些信息相關聯，也許將這些信息與其他信息中包含的其他信息合併。合成一組二維點的算法

問題是，我必須創建一個新的集合，所有對點之間的最小距離受到尊重，最少的信息已經丟失。

我不能想到一個算法或方法，以任何時間成本解決這個問題。

任何幫助，將不勝感激。

來源

2015-09-20 manelmc

你的問題不清楚。你能證明一個例子，你有什麼嘗試？ – barak1412

@ barak1412我編輯了描述，現在更清楚了嗎？ – manelmc

也許聚集2D點是你正在尋找的。（https://en.wikipedia.org/wiki/Cluster_analysis） – barak1412

天真的 - 並不快（O（N 3）），但可以讓你開始：

查找任意兩點之間的最小距離，即一對在全球有最小距離分（Ø （N²））
如果距離小於所需的最小值，你做
合併這兩個點，並在1

這開始大融合是最併攏一個由上分e使用蠻力算法，直到達到最小距離。如在所述的評論中提到的那樣，可以在O（n log n）中找到關閉對，如例如所描述的。在相應的維基百科文章（其中包括一些動態方面的討論可能在這裏很有用）：https://en.wikipedia.org/wiki/Closest_pair_of_points_problem

來源

2015-09-20 18:47:05

謝謝Stefan，這是一個開始。讓我們看看它是如何響應。 – manelmc

最近的點對問題在時間'O（N Log（N））'中解決。合併點使其成爲問題的動態實例。我不會感到驚訝的是，下一個查詢可以在時間O（Log（N））左右執行，從而導致比O（N 3）更好的複雜性。 –

這裏有一個k-d樹。 O（N日誌N）來構建。 O（log N）找到最近的鄰居O（log N）來刪除一個點。使用優先級隊列來確定下兩個最近的點。 – Nuclearman

合成一組二維點的算法

回答

相關問題