标题是大多数问题.我有一组圆圈,每个圆圈由中心C和半径r给出.两个圆之间的距离是它们中心之间的欧氏距离减去它们的半径.对于圆圈a和b,
d_ab = | C_a - C_b | - r_a - r_b.
请注意,如果圆圈重叠,这可能是负数.
那么找到集合中给定圆的最近(最小距离)邻居的最快数据结构是什么？
必须支持添加和删除以"任意顺序交错"的"查找最近"查询的圆圈.事先没有人知道该集的几何分布.
这将是系统的核心,其中典型的圈数为50,000,并且将需要成千上万的查询,插入和删除,理想情况是高端平板设备上的用户交互速度(一秒或更短).
该点最近的邻居进行了研究,死亡,但这个版本与圈似乎有点困难.
我看过kd-trees,四棵树,r-trees以及这些变种.关于哪些可能是最好的尝试以及新建议的建议都将是一个非常好的帮助.