我正在寻找一个良好的功能数据结构来存储空间（点）数据。数据结构应允许对已存在的点进行简单的epsilon查询。我还需要经常修改数据。这意味着点可以移动，并且应该能够在数据结构中更新。这可以使用普通的删除/添加来处理，但真正的移动可能会更快。
现在我正在考虑使用 四/八树 （或更高），因为移动部分应该很容易做到。然而，就平衡而言，已知四棵树更糟糕。 KD树 可能是另一种选择，但更新似乎非常讨厌。我能找到的大多数空间数据结构实现只是程序性的，我使用的是函数式语言。
我正在寻找一个良好的功能数据结构来存储空间（点）数据。数据结构应允许对已存在的点进行简单的epsilon查询。我还需要经常修改数据。这意味着点可以移动，并且应该能够在数据结构中更新。这可以使用普通的删除/添加来处理，但真正的移动可能会更快。
现在我正在考虑使用 四/八树 （或更高），因为移动部分应该很容易做到。然而，就平衡而言，已知四棵树更糟糕。 KD树 可能是另一种选择，但更新似乎非常讨厌。我能找到的大多数空间数据结构实现只是程序性的，我使用的是函数式语言。
根据您的使用方式以及快速移动点数，您可能还会考虑 扫和修剪。基本上，您将点保持在一个维度（例如x）中。如果点很少更改位置，则每个模拟步骤的运行插入排序实际上非常快。
（顺便说一下，我认为你的两个建议已经很好了）
这篇旧报纸 由Overmars和van Leeuwen描述 伪四叉树 - 四叉树，当插入和删除进展时，它也可以平衡自身。插入和删除的摊销成本是这样的 O(log^d(n)) 甚至可以与完成的平衡量进行交易（你可以在论文中阅读更多相关信息）。
R-树 和R * -Trees也是另一种解决方案，易于实现。
看到 https://github.com/mariusaeriksen/ocaml-rtree （在OCaml中）举个例子。
我在疏散模拟中使用它们，更新步骤并不是那么慢。