{"ID":2829722,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.11299","arxiv_id":"2512.11299","title":"Shortest Paths on Convex Polyhedral Surfaces","abstract":"Let $\\mathcal{P}$ be the surface of a convex polyhedron with $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(n^{8+ε})$ preprocessing time and space [Aggarwal, Aronov, O'Rourke, and Schevon, SICOMP 1997], where $ε$ is an arbitrarily small positive constant. In this paper, we present a new data structure of $O(n^{6+ε})$ preprocessing time and space, with $O(\\log n)$ query time. For a special case where one query point is required to lie on one of the edges of $\\mathcal{P}$, the previously best work uses $O(n^{6+ε})$ preprocessing time and space to achieve $O(\\log n)$ query time. We improve the preprocessing time and space to $O(n^{5+ε})$, with $O(\\log n)$ query 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 $Θ(n^4)$ in number and have a total complexity of $Θ(n^5)$ in the worst case. The previously best algorithm for the problem takes roughly $O(n^6\\log n\\log^*n)$ time, while our new algorithm runs in $O(n^{5+ε})$ time.","short_abstract":"Let $\\mathcal{P}$ be the surface of a convex polyhedron with $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....","url_abs":"https://arxiv.org/abs/2512.11299","url_pdf":"https://arxiv.org/pdf/2512.11299v1","authors":"[\"Haitao Wang\"]","published":"2025-12-12T05:51:45Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DS\"]","methods":"[]","has_code":false}