EPSILON-NETS AND SIMPLEX RANGE QUERIES
EPSILON-NETS AND SIMPLEX RANGE QUERIES
复制标题
DOI：
10.1007/bf02187876
复制
发表时间：
1987-01-01
影响因子：
0.8
通讯作者：
WELZL, E
中科院分区：
文献类型：
--
作者：
HAUSSLER, D;WELZL, E
提出了一种利用Ο(N)空间和Ο(NA)查询时间进行半空间和单纯形范围查询的新技术，其中a<；d(d-1)/d(d-1)+1+γ对所有维度d≥2和γ>；0。这些界限比以前发表的针对ALLD≥2的界限更好。该技术使用随机抽样来建立分区树结构。我们引入了抽象值域集的ε网的概念来描述随机抽样的期望结果，并给出了随机抽样是高概率ε网的充要条件。我们举例说明了这些思想在其他范围查询问题中的应用。
We present a new technique for half-space and simplex range query usingΟ(n) space andΟ(na) query time, wherea<d(d-1)/d(d-1) + 1 + γ for all dimensionsd≥ 2 andγ> 0. These bounds are better than those previously published for alld≥ 2. The technique uses random sampling to build a partition-tree structure. We introduce the concept of anε-net for an abstract set of ranges to describe the desired result of this random sampling and give necessary and sufficient conditions that a random sample is anε-net with high probability. We illustrate the application of these ideas to other range query problems.