标题： 凸性有助于三维中的迭代搜索 显示英文标题

标题： Convexity Helps Iterated Search in 3D

摘要： 受经典的分数级联技术的启发，我们引入了新方法以加速三维中的以下类型的迭代搜索：输入是一个具有有界度数的图$\mathbf{G}$以及与$\mathbf{G}$的每个顶点$v$关联的一组 3D 超平面$H_v$。 目标是存储输入，使得对于一个查询点 $q\in \mathbb{R}^3$ 和一个连通子图 $\mathbf{H}\subset \mathbf{G}$，我们可以判断对于每个 $v\in \mathbf{H}$，$q$ 是否位于 $H_v$ 的下包络的下方或上方。 我们证明了使用线性空间，可以在大约 $O(\log n + |\mathbf{H}|\sqrt{\log n})$ 的时间内回答查询，这改进了通过使用平面点定位数据结构得到的平凡界 $O(|\mathbf{H}|\log n)$。 我们的数据结构实际上可以回答更通用的查询（它可以与浅层切割结合），并且即使当$\mathbf{H}$一个接一个地给出顶点时，它仍然有效。 我们展示了这带来了许多新的应用，并且特别地，我们给出了对一组自然的数据结构问题的改进解决方案，据我们所知，这些问题之前没有取得过任何进展。 我们认为这是一个非常令人惊讶的结果，因为对于平面点定位问题，获得类似的结果被证明是不可能的。 显示英文摘要

摘要： Inspired by the classical fractional cascading technique, we introduce new techniques to speed up the following type of iterated search in 3D: The input is a graph $\mathbf{G}$ with bounded degree together with a set $H_v$ of 3D hyperplanes associated with every vertex of $v$ of $\mathbf{G}$. The goal is to store the input such that given a query point $q\in \mathbb{R}^3$ and a connected subgraph $\mathbf{H}\subset \mathbf{G}$, we can decide if $q$ is below or above the lower envelope of $H_v$ for every $v\in \mathbf{H}$. We show that using linear space, it is possible to answer queries in roughly $O(\log n + |\mathbf{H}|\sqrt{\log n})$ time which improves trivial bound of $O(|\mathbf{H}|\log n)$ obtained by using planar point location data structures. Our data structure can in fact answer more general queries (it combines with shallow cuttings) and it even works when $\mathbf{H}$ is given one vertex at a time. We show that this has a number of new applications and in particular, we give improved solutions to a set of natural data structure problems that up to our knowledge had not seen any improvements. We believe this is a very surprising result because obtaining similar results for the planar point location problem was known to be impossible.