论文标题
重新访问单纯范围搜索：如何在多级数据结构中剃须日志
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
论文作者
论文摘要
我们重新审视了单纯范围搜索和计算几何相关问题的经典问题。我们提供了一系列新结果，这些结果通过使用多级数据结构引起的多个对数因素提高了以前的界限。亮点包括以下内容： $ \ bullet $用于一组$ n $点在常数尺寸$ d $中的$ n $点，我们提供$ o（n^d）$（或稍好）空间的数据结构，可以回答最佳$ o（\ log n）$ time and simplex范围中的单纯范围计数查询中的查询，以最佳$ o（\ log n + k）$ k $ k $ k $ k $ DENOTES the Uptive size the UppertionS size the Uppertions size youtpers $ o（对于semigroup范围搜索，我们获得$ o（\ log n）$查询时间，并使用$ o（n^d \ mathop {\ rm polylog} n）$ space。 Matoušek的先前数据结构的近三十年前具有相似的空间界限，$ O（\ log^{d+1} n）$或$ o（\ log^{d+1} n+k）$查询时间。 $ \ bullet $用于在恒定尺寸$ d $中的一组$ n $简单，我们提供具有$ o（n）$空间的数据结构，可以回答刺伤计数查询（计数包含查询点的简单数量）$ o（n^{1-1/d}）$ o（n^{1-1/d}）$时间，以及$ o（n^n^1-1/d} $ o（n^n^1-1/d）$ o（n^{1-1/d）$ o（n^{1-1/d以前的数据结构在空间和查询时间中具有额外的$ \ log^d n $因子。 $ \ bullet $用于一组$ n $（可能是相交的）线段的$ \ bullet $，在2D中，我们使用$ o（n）$ space提供了一个数据结构，可以回答$ o（\ sqrt {n}）$时间的射线拍摄查询。这可以用$ O（n \ log n）$ space和$ o（\ sqrt {n} \ log n）$查询时间来改善Wang最近的数据结构[SOCG'20]。
We revisit the classic problem of simplex range searching and related problems in computational geometry. We present a collection of new results which improve previous bounds by multiple logarithmic factors that were caused by the use of multi-level data structures. Highlights include the following: $\bullet$ For a set of $n$ points in a constant dimension $d$, we give data structures with $O(n^d)$ (or slightly better) space that can answer simplex range counting queries in optimal $O(\log n)$ time and simplex range reporting queries in optimal $O(\log n + k)$ time, where $k$ denotes the output size. For semigroup range searching, we obtain $O(\log n)$ query time with $O(n^d\mathop{\rm polylog}n)$ space. Previous data structures with similar space bounds by Matoušek from nearly three decades ago had $O(\log^{d+1}n)$ or $O(\log^{d+1}n + k)$ query time. $\bullet$ For a set of $n$ simplices in a constant dimension $d$, we give data structures with $O(n)$ space that can answer stabbing counting queries (counting the number of simplices containing a query point) in $O(n^{1-1/d})$ time, and stabbing reporting queries in $O(n^{1-1/d}+k)$ time. Previous data structures had extra $\log^d n$ factors in space and query time. $\bullet$ For a set of $n$ (possibly intersecting) line segments in 2D, we give a data structure with $O(n)$ space that can answer ray shooting queries in $O(\sqrt{n})$ time. This improves Wang's recent data structure [SoCG'20] with $O(n\log n)$ space and $O(\sqrt{n}\log n)$ query time.
