论文标题
正交范围报告和范围最小查询的新数据结构
New Data Structures for Orthogonal Range Reporting and Range Minima Queries
论文作者
论文摘要
在本文中，我们为正交范围搜索问题的两个广泛研究的变体提供了新的数据结构。 首先，我们描述了一个支持二维正交范围的数据结构，以$ o（n）$空间和$ o（\ log^{\ varepsilon} n）$ time中的最小值查询，其中$ n $是数据结构中的点数，$ \ varepsilon $是一个任意的小正常常数。此问题的先前已知的线性空间解决方案需要$ o（\ log^{1+ \ varepsilon} n）$（Chazelle，1988）或$ O（\ log n \ log log \ log \ log n）$ time（Farzan等，2012）。我们数据结构的修改使用Space $ O（N \ Log \ log n）$，并支持时间$ o（\ log \ log n）$的最小查询。两种结果都可以扩展以支持三维五面报告查询。 接下来，我们转到四维正交范围报告问题，并提出一个数据结构，该数据结构回答最佳$ o（\ log n/\ log \ log \ log \ log n + k）$时间，其中$ k $是答案中的点数。这是实现此问题最佳查询时间的第一个数据结构。 我们的结果是通过利用三维浅插条的性质获得的。
In this paper we present new data structures for two extensively studied variants of the orthogonal range searching problem. First, we describe a data structure that supports two-dimensional orthogonal range minima queries in $O(n)$ space and $O(\log^{\varepsilon} n)$ time, where $n$ is the number of points in the data structure and $\varepsilon$ is an arbitrarily small positive constant. Previously known linear-space solutions for this problem require $O(\log^{1+\varepsilon} n)$ (Chazelle, 1988) or $O(\log n\log \log n)$ time (Farzan et al., 2012). A modification of our data structure uses space $O(n\log \log n)$ and supports range minima queries in time $O(\log \log n)$. Both results can be extended to support three-dimensional five-sided reporting queries. Next, we turn to the four-dimensional orthogonal range reporting problem and present a data structure that answers queries in optimal $O(\log n/\log \log n + k)$ time, where $k$ is the number of points in the answer. This is the first data structure that achieves the optimal query time for this problem. Our results are obtained by exploiting the properties of three-dimensional shallow cuttings.
