nearest-neighbor - 最近傍2次元

Question

2次元空間内の点のセットSが与えられた場合、セット内の各点の最近傍（ユークリッド）を計算するアルゴリズムを提供します。最隣グラフと呼ばれていると思いますよね？既存の効率的なアルゴリズム（N log N）、ここでN = len（S）？

Answer 1

kd-treeは、最近傍検索の非常に標準的なアルゴリズムです (2 空間であっても、最初の図に惑わされないでください) 。