论文标题
在几乎最佳时间内，指针机模型中的4D范围报告
4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time
论文作者
论文摘要
在正交范围的报告问题中，我们必须预处理多维点的$ p $，以便可以有效地报告来自$ q \ cap p $的任何轴平行查询矩形$ q $ q $ q。在本文中，我们研究了指针机模型中多维正交范围报告的查询复杂性。我们提出了一个数据结构，该数据结构在几乎最佳的时间$ o（\ log n \ log \ log \ log n + k）$中回答四维正交范围报告查询，并使用$ o（n \ log^4 n）$ space，其中$ n $是$ p $ and $ k $中的点数，$ k $是$ q \ q \ q \ cap cap p $ p $。这是第一个具有几乎线性空间用法的数据结构，在4D中实现了几乎最佳的查询时间。该结果可以立即推广到$ d \ ge 4 $尺寸：我们表明，有一个数据结构支持$ d $ - 二维范围报告时间$ o（\ log^{d-3} n \ log \ log \ log \ log \ log \ log n+k）$对于任何常数$ d \ ge 4 $。
In the orthogonal range reporting problem we must pre-process a set $P$ of multi-dimensional points, so that for any axis-parallel query rectangle $q$ all points from $q\cap P$ can be reported efficiently. In this paper we study the query complexity of multi-dimensional orthogonal range reporting in the pointer machine model. We present a data structure that answers four-dimensional orthogonal range reporting queries in almost-optimal time $O(\log n\log\log n + k)$ and uses $O(n\log^4 n)$ space, where $n$ is the number of points in $P$ and $k$ is the number of points in $q\cap P$ . This is the first data structure with nearly-linear space usage that achieves almost-optimal query time in 4d. This result can be immediately generalized to $d\ge 4$ dimensions: we show that there is a data structure supporting $d$-dimensional range reporting queries in time $O(\log^{d-3} n\log\log n+k)$ for any constant $d\ge 4$.
