# Shortest Paths on Convex Polyhedral Surfaces

Preprint · Haitao Wang

- Archive id: arxiv:2512.11299
- Published: 2025-12-12
- arXiv: https://arxiv.org/abs/2512.11299
- Citations: 0
- Source URL: https://arxiv.org/abs/2512.11299
- PDF: https://arxiv.org/pdf/2512.11299
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.