Quasi-optimal range searching in spaces of finite VC-dimension
Quasi-optimal range searching in spaces of finite VC-dimension
复制标题
有限VC维空间中的拟最优范围搜索
DOI：
--
复制
发表时间：
1989
影响因子：
0.8
通讯作者：
E. Welzl
中科院分区：
文献类型：
--
作者：
B. Chazelle;E. Welzl
允许有效分区树的范围搜索问题是由有限的Vapnik-Chervonenkis尺寸定义的，这些问题更一般地表明这些问题是唯一可以在Arithmetic中使用sublinear Query时间的线性解决方案的问题模型。处理最常见的范围搜索问题的技术，例如单纯形和球形范围搜索。边缘。访问机器一劳永逸地修复（如三角形范围搜索），存储需求也会下降（n）。 log2n）查询时间。我们介绍了三个空间INO（N2/3 log2n）查询时间的ANO（n logn）尺寸数据结构。可以在多项式时间内完成。
The range-searching problems that allow efficient partition trees are characterized as those defined by range spaces of finite Vapnik-Chervonenkis dimension. More generally, these problems are shown to be the only ones that admit linear-size solutions with sublinear query time in the arithmetic model. The proof rests on a characterization of spanning trees with a low stabbing number. We use probabilistic arguments to treat the general case, but we are able to use geometric techniques to handle the most common range-searching problems, such as simplex and spherical range search. We prove that any set ofn points inEd admits a spanning tree which cannot be cut by any hyperplane (or hypersphere) through more than roughlyn1−1/d edges. This result yields quasi-optimal solutions to simplex range searching in the arithmetic model of computation. We also look at polygon, disk, and tetrahedron range searching on a random access machine. Givenn points inE2, we derive a data structure of sizeO(n logn) for counting how many points fall inside a query convexk-gon (for arbitrary values ofk). The query time isO(√kn logn). Ifk is fixed once and for all (as in triangular range searching), then the storage requirement drops toO(n). We also describe anO(n logn)-size data structure for counting how many points fall inside a query circle inO(√n log2n) query time. Finally, we present anO(n logn)-size data structure for counting how many points fall inside a query tetrahedron in 3-space inO(n2/3 log2n) query time. All the algorithms are optimal within polylogarithmic factors. In all cases, the preprocessing can be done in polynomial time. Furthermore, the algorithms can also handle reporting within the same complexity (adding the size of the output as a linear term to the query time).