K-d Tree for Semidynamic Point Set

K-d Tree for Semidynamic Point Setを実装してみました。semi-なのは、（再構築しない限り）頂点の追加を認めていないからだと思います。

Javaソフトウェアの無料ダウンロード

アプレットの動作には、Sun MicrosystemsのJ2SE5.0以上が必要です。

左クリック

頂点の追加してデータ構造を再構築

右クリック

最近傍検索

質問は青、質問に対する最近傍頂点は赤で塗りつぶしています。

Median値はクイックソートを元に計算しています。クイックソートするよりは高速なはずです。

最近傍検索は、Top-Downで検索しています。

参考文献

• Bentley, J. L. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (Sep. 1975), 509–517.
• Bentley, J. L. 1990. K-d Trees for Semidynamic Point Sets. SCG ‘90: Proc. 6th Annual Symposium on Computational Geometry (1990), 187–197