Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
Pankaj K. Agarwal · SIAM Journal on Computing · 1992
This paper considers the following problem: Given a set $\mathcal{G}$ of n (possibly intersecting) line segments in the plane, preprocess it so that, given a query ray $\rho $ emanating from a point p, one can quickly compute the intersection point $\Phi (\mathcal{G},\rho )$ of $\rho $ with a segment of $\mathcal{G}$ that lies nearest to p. The paper presents an algorithm that preprocesses $\mathcal{G}$, in time $O(n^{3/ 2} \log^\omega n)$, into a data structure of size $O(n\alpha (n)\log ^4 n)$, so that for a query ray $\rho $, $\Phi (\mathcal{G},\rho )$ can be computed in time $O(\sqrt {n\alpha (n)} \log ^2 n)$, where $\omega $ is a constant $ < 4.33$ and $\alpha (n)$ is a functional inverse of Ackermann’s function. If the given segments are nonintersecting, the storage goes down to $O(n\log ^3 n)$ and the query time becomes $O(\sqrt n \log ^2 n)$. The main tool used is spanning trees (on the set of segment endpoints) with low stabbing number, i.e., with the property that no line intersects more than $O(\sqrt n )$ edges of the tree. Such trees make it possible to obtain faster algorithms for several other problems, including implicit point location, polygon containment, and implicit hidden surface removal.