沃罗诺图
组合数学
数学
三角测量
随机算法
计算几何
树(集合论)
二进制对数
点位
算法
欧几里得空间
欧米茄
近似算法
点(几何)
离散数学
物理
量子力学
几何学
摘要
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 diagram of the input points, and is a considerable improvement over previous bounds for $d > 3$. The main step of the construction algorithm is the determination of the Voronoi diagram of a random sample of the sites, and the triangulation of that diagram.
科研通智能强力驱动
Strongly Powered by AbleSci AI