在2D平面中給定的一組點中找到兩個點，其中距離最短的距離小於O（n^2）

Question

我在雅虎被問及機器學習配置文件的這個問題。給定一組點（x，y）座標，我被要求在O（n）或O（log n）時間內找到距離最近的點。 很明顯，我能夠拿出O（n^2）的時間，但沒法獲得更好的算法。儘管問題陳述尖叫分而治之，但我無法想出合併步驟的推理。我也在互聯網上搜索這個問題，發現它實際上非常受歡迎，但我仍然無法理解合併步驟的推理。

任何人都可以幫我解決這個問題嗎？

輸入：（X1，Y1），（X2，Y2），（X3，Y3），（X4，Y4），（X5，Y5）

Answer 1

的問題可以在O解決（N日誌N ）時間使用遞歸除法和征服方法，例如，如下所示：

1.根據它們的x座標排序點。

2.通過垂直線x = xmid將這組點分成兩個相同大小的子集。

3.在左側和右側子集中遞歸解決問題。這產生了分別的左側和右側最小距離dLmin和dRmin。

4.找出一對點位於分割垂直線左側，第二個點位於右側的一對點之間的最小距離dLRmin。

5.最終答案是dLmin，dRmin和dLRmin中的最小值。

http://en.wikipedia.org/wiki/Closest_pair_of_points