Shortest Paths on Convex Polyhedral Surfaces

Let $\mathcal{P}$ be the surface of a convex polyhedron of n vertices. We consider the two-point shortest path query problem for $\mathcal{P}$: Constructing a data structure so that given any two query points s and t on $\mathcal{P}$, a shortest path from s to t on $\mathcal{P}$ can be computed efficiently. To achieve $O(\log n)$ query time (for computing the shortest path length), the previously best result uses $O\left(n^{8+\epsilon}\right)$ preprcessing time and space [Aggarwal, Aronov, O’Rourke, and Schevon, SICOMP 1997], where $\epsilon$ is an arbitrarily small positive constant. In this paper, we present a new data structure of $O\left(n^{6+\frac{2}{3}+\epsilon}\right)$ preprocessing time and space, with $O(\log n)$ query time. For a special case where one query point is required to be on an edge of $\mathcal{P}$, the previously best work uses $O\left(n^{6+\epsilon}\right)$ preprcessing time and space to achieve $O(\log n)$ query time. We improve the preprocessing time and space to $O\left(n^{5+\frac{1}{4}+\epsilon}\right)$, with $O(\log n)$ query time. If both query points are on the edges of $\mathcal{P}$, then we can answer each query in $O(\log n)$ time with $O\left(n^{5+\epsilon}\right)$ space and preprocessting time. Furthermore, we present a new algorithm to compute the exact set of shortest path edge sequences of $\mathcal{P}$, which are known to be $\Theta\left(n^{4}\right)$ in number and have a total complexity of $\Theta\left(n^{5}\right)$ in the worst case. The previously best algorithm for the problem takes roughly $O\left(n^{6} \log n \log ^{*} n\right)$ time, while our new algorithm runs in $O\left(n^{5+\epsilon}\right)$ time.