在n维空间上进行快速近邻搜索的纯函数数据结构是什么?

Question

我正在寻找一个纯功能的数据结构与API，如:

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

或者它的一些变化，在n维空间中提供对最近元素的快速插入、删除和查询。数据结构是什么?

Answer 1

有一个从二维到n的四叉树的自然推广。

Answer 2

对于n维空间，也存在k-d树。