Polytope range searching and integral geometry
Polytope range searching and integral geometry
复制标题
多面体范围搜索和积分几何
DOI：
10.1109/sfcs.1987.48
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
B. Chazelle
中科院分区：
文献类型：
--
作者：
B. Chazelle
plexity ofsimplex range searching. We prove that the worst-case query time is 0. (n/vm), for d = 2, and more generally, 0. (nl log n)/m 1 / d ) , for d ~ 3; n is the number of points and m is the amount of stor age available. These bounds hold with high probability for a random point-set (from a uniform distribution) and thus are valid in the worst case as well as on the average. Interestingly, they still hold if the query remains congruent to a fixed simplex or even a fixed slab. What is the significance of these lower bounds? From a practical standpoint the news is disheartening but instructive. For the sake of il lustration, take d = 11: our results say that with only linear storage the query time will have to be at least 0'(nO. 9 ). To make matters worse, this quasi-linear lower bound also holds on the average, so it is un escapable in practice. For the query time to be lowered to, say, O(y'n), one would need g(n S ) storage, and a whopping n(n 10 ) space would be necessary if a polylogarithmic query time were desired. Things are
