最近的一對點使用分而治之算法來計算在合併階段只有6點

Question

這是一個問題出現在科爾曼的Algos介紹的基礎上找到最接近的一對點，其中Y'屬於垂直帶距離線「l」至少有一些「三角」距離的點。 d是除法和征服階段計算的任意一對點之間的最小距離。 P是點的集合，PL是分割後的左邊的點集合，PR是正確的點集合。

威廉姆斯教授提出了一種方案，允許最接近對算法僅檢查數組Y'中每個點之後的5個點。這個想法總是將第l行的點放入PL中。然後，在線l上不能有一對重合點，一個在PL中，一個在PR中。因此，最多6個點可以駐留在dx2d矩形上。這個算法有什麼缺陷？

Answer 1

第一個直覺：使用這種策略，您可能無法將點集合拆分成平衡子集，從而影響臨時行爲（想象垂直上的所有點）。