Further Results on Colored Range Searching
Further Results on Colored Range Searching
复制标题
DOI：
10.4230/lipics.socg.2020.28
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Timothy M. Chan;Qizheng He;Yakov Nekrich
中科院分区：
文献类型：
--
作者：
Timothy M. Chan;Qizheng He;Yakov Nekrich
我们提供了许多有关搜索有色（或“分类”）数据的范围的新结果：1。对于三个维度的一组$ n $彩色点，我们用$ o（n \ mathop {\ rm {\ rm）描述了随机数据结构polygog} n）$ space可以在任何查询正交范围（与轴对准框）中报告不同的颜色（k \ mathop {\ rm） polyloglog} n）$预期时间，其中$ k $是该范围内不同颜色的数量，假设坐标为$ \ {1，\ ldots，n \} $。先前的数据结构要求$ o（\ frac {\ log n} {\ log \ log n} + k）$查询时间。我们的结果也意味着改善较高的恒定维度。 2。我们的数据结构可以在三个维度（或二维中的圆形范围）中适应半空间范围，从而实现$ O（k \ log n）$预期查询时间。先前的数据结构需要$ O（k \ log^2n）$查询时间。 3。对于二维中的$ n $彩色点，我们用$ o（n \ mathop {\ rm polylog} n）$ space描述一个数据结构在查询正交范围内每种不同颜色的出现数量。查询时间为$ o（\ frac {\ log n} {\ log \ log n} + k \ log \ log \ log n）$，其中$ k $是该范围内不同颜色的数量。天真执行$ k $未颜色的范围计数查询将需要$ o（k \ frac {\ log n} {\ log \ log \ log n}）$ time。我们的数据结构是使用各种技术设计的，包括随机增量结构的彩色变体（可能是独立感兴趣的），浅插曲的彩色变体以及填充位的技巧。
We present a number of new results about range searching for colored (or "categorical") data: 1. For a set of $n$ colored points in three dimensions, we describe randomized data structures with $O(n\mathop{\rm polylog}n)$ space that can report the distinct colors in any query orthogonal range (axis-aligned box) in $O(k\mathop{\rm polyloglog} n)$ expected time, where $k$ is the number of distinct colors in the range, assuming that coordinates are in $\{1,\ldots,n\}$. Previous data structures require $O(\frac{\log n}{\log\log n} + k)$ query time. Our result also implies improvements in higher constant dimensions. 2. Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving $O(k\log n)$ expected query time. Previous data structures require $O(k\log^2n)$ query time. 3. For a set of $n$ colored points in two dimensions, we describe a data structure with $O(n\mathop{\rm polylog}n)$ space that can answer colored "type-2" range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is $O(\frac{\log n}{\log\log n} + k\log\log n)$, where $k$ is the number of distinct colors in the range. Naively performing $k$ uncolored range counting queries would require $O(k\frac{\log n}{\log\log n})$ time. Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks.