n次元空間上で最近傍探索を高速に行うための純粋に機能的なデータ構造とは何ですか？

Question

私は、次のようなAPIを純粋に機能的なデータ構造を探しています：n次元空間における最も近い要素のための高速挿入、削除、クエリを提供する、

insert :: Vector n Int -> Struct n -> Struct n 
remove :: Vector n Int -> Struct n -> Struct n 
nearest :: Vector n Int -> Struct n -> Vector n Int 

か、そのいくつかのバリエーション。そのデータ構造とは何ですか？

Answer 1

2次元からnまでのquadtreesの自然な一般化があります。

Answer 2

n次元空間については、k-d treeもあります。