A Randomized Algorithm for Closest-Point Queries
A Randomized Algorithm for Closest-Point Queries
复制标题
最近点查询的随机算法
DOI：
10.1137/0217052
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
K. Clarkson
中科院分区：
文献类型：
--
作者：
K. Clarkson
给出了最近点查询的算法。问题是这样的：给定 d 维空间中 n 个点的集合 S，构建一个数据结构，以便给定任意查询点 p，可以快速找到 S 中距离 p 最近的点。距离的度量是欧几里得范数。这有时称为邮局问题。新的数据结构将被称为 RPO 树，来自随机邮局。对于任何固定的 $\epsilon > 0$，构建 RPO 树所需的预期时间为 $O(n^{\lceil {{d / 2}} \rceil (1 + \epsilon )} )$，并且在最坏情况下可以在 $O(\log n)$ 时间内回答查询。在最坏的情况下，RPO 树需要 $O(n^{\lceil {{d / 2}} \rceil (1 + \epsilon )} )$ 空间。这些界限中的常数因子取决于 d 和 $\epsilon $。由于算法采用的随机化，界限是平均情况，并且适用于任何输入点集。该结果接近构建 Voronoi 的任何算法所需的 $\Omega (n^{\lceil {{d / 2}} \rceil } )$ 最坏情况时间...
An algorithm for closest-point queries is given. The problem is this: given a set S of n points in d-dimensional space, build a data structure so that given an arbitrary query point p, a closest point in S to p can be found quickly. The measure of distance is the Euclidean norm. This is sometimes called the post-office problem. The new data structure will be termed an RPO tree, from Randomized Post Office. The expected time required to build an RPO tree is $O(n^{\lceil {{d / 2}} \rceil (1 + \epsilon )} )$, for any fixed $\epsilon > 0$, and a query can be answered in $O(\log n)$ worst-case time. An RPO tree requires $O(n^{\lceil {{d / 2}} \rceil (1 + \epsilon )} )$ space in the worst case. The constant factors in these bounds depend on d and $\epsilon $. The bounds are average-case due to the randomization employed by the algorithm, and hold for any set of input points. This result approaches the $\Omega (n^{\lceil {{d / 2}} \rceil } )$ worst-case time required for any algorithm that constructs the Voronoi...