On Range Searching with Semialgebraic Sets II
On Range Searching with Semialgebraic Sets II
复制标题
半代数集的范围搜索 II
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Sharir
中科院分区：
文献类型：
--
作者：
P. Agarwal;J. Matoušek;M. Sharir
让P为RD中的一组n个点单纯范围搜索的类似结构，以及D≥5的范围，从1994年获得的前两个作者显着改善了早期的解决方案。这几乎解决了范围搜索的长期开放问题结构基于Guth和Katz的多项式分区技术[Arxiv：1011.4105]，该技术表明，对于参数r，1 <r≤n;因此，RD z（f）的每个连接组件都包含p的n/r点，其中z（f）是f的零集，我们提出了一种有效的随机算法，用于计算这种多项式分区兴趣和是可能有其他申请。
Let P be a set of n points in Rd. We present a linear-size data structure for answering range queries on P with constant-complexity semialgebraic sets as ranges, in time close to O(n1-1/d). It essentially matches the performance of similar structures for simplex range searching, and, for d ≥ 5, significantly improves earlier solutions by the first two authors obtained in 1994. This almost settles a long-standing open problem in range searching. The data structure is based on the polynomial-partitioning technique of Guth and Katz [arXiv:1011.4105], which shows that for a parameter r, 1 <; r ≤ n, there exists a d-variate polynomial f of degree O(r1/d) such that each connected component of Rd Z(f) contains at most n/r points of P, where Z(f) is the zero set of f. We present an efficient randomized algorithm for computing such a polynomial partition, which is of independent interest and is likely to have additional applications.