Maintaining the minimal distance of a point set in polylogarithmic time
Maintaining the minimal distance of a point set in polylogarithmic time
复制标题
在多对数时间内保持点集的最小距离
DOI：
10.1007/bf02187852
复制
发表时间：
1992
影响因子：
0.8
通讯作者：
M. Smid
中科院分区：
文献类型：
--
作者：
M. Smid
给出了一种动态数据结构，它在一个由n个点组成的墨水维空间中保持最小距离，每次更新的平摊时间为inO（(logn)k log logn）。数据结构的大小以o （n(logn)k）为界。距离用minkowskill -metric度量，其中1≤t≤∞。这是第一个在多对数时间内保持最小距离的动态数据结构，可以完全在线更新。
A dynamic data structure is given that maintains the minimal distance in a set ofn points ink-dimensional space inO((logn)k log logn) amortized time per update. The size of the data structure is bounded byO(n(logn)k). Distances are measured in the MinkowskiLt-metric, where 1 ≤t ≤ ∞. This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time for fully on-line updates.