二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？…

二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです １．集合Pはあらかじめ、任意の順番でソートしておける ２．点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです 集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか？ みなさんのアイディアを貸してください

[tomtom35]

“http://ja.wikipedia.org/wiki/%E6%9C%80%E8%BF%91%E5%82%8D%E6%8E%A2%E7%B4%A2”

[yaotti]

「四分木」、「kd木」、「VP木」ボロノイ図

[suu-g]

R木 via yaotti, SS-Tree SR-Tree M-Tree LSH(Locality-Sensitive Hashing) via 404 comments

[okagawa]

四分木、kd木、VP木。衝突判定アルゴリズム

[paella]

良い質問に良い回答（コメント欄も）。あとはこれが学校の宿題でないことを祈るのみ。

[n4_t]

四分木 kd木 VP木 ボロノイ図