Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique
Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique
复制标题
动态广义最近对：重温 Eppstein 的技术
DOI：
10.1137/1.9781611976014.6
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Chan, Timothy M.
中科院分区：
文献类型：
--
作者：
Chan, Timothy M.
Eppstein（1995）给出了一种技术，可以将任何用于动态最近邻查询的数据结构转换为用于动态最近对的数据结构，对于任何距离函数;该转换将时间限制增加了两个对数因子。我们提出了一个类似的简单的变换，它同样好，并且可以避免额外的对数因子，当给定结构的查询和更新时间为n时，对于某个常数n> 0。因此，在任意距离函数的情况下，我们得到了一个O（n）空间的最优数据结构，以保持动态最近对的n个点在O（n）摊销时间加上O（n）每次更新的距离计算。
Eppstein (1995) gave a technique to transform any data structure for dynamic nearest neighbor queries into a data structure for dynamic closest pair, for any distance function; the transformation increases the time bound by two logarithmic factors. We present a similar, simple transformation that is just as good, and can avoid the extra logarithmic factors when the query and update time of the given structure exceedn∊for some constant∊> 0.Consequently, in the case of an arbitrary distance function, we obtain an optimalO(n)-space data structure to maintain the dynamic closest pair ofnpoints inO(n)amortized time plusO(n) distance evaluations per update.
登录
查看更多内容
廉价飞行：关于最低燃油消耗问题
DOI：
--
发表时间：
2001
期刊：
J. Algorithms
影响因子：
--
作者：
Timothy M. Chan;A. Efrat
通讯作者：
A. Efrat
DOI：
--
发表时间：
1998
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
D. Eppstein
通讯作者：
D. Eppstein
DOI：
--
发表时间：
1991
期刊：
JACM
影响因子：
--
作者：
D. Dobkin;S. Suri
通讯作者：
S. Suri
3维排列中浅层的垂直分解及其应用
DOI：
10.1145/220279.220284
发表时间：
1995
期刊：
--
影响因子：
--
作者：
P. Agarwal;A. Efrat;M. Sharir
通讯作者：
M. Sharir
影响因子：
0.8
作者：
Chan, Timothy M.
通讯作者：
Chan, Timothy M.