Shortest Path Map Equivalence Decompositions and Applications
2026-07-03 • Computational Geometry
Computational GeometryData Structures and Algorithms
AI summaryⓘ
The authors study how to divide a polygonal shape into regions based on the pattern of shortest paths from a specific point inside it. They define these divisions so that inside each region, the shortest paths share the same route structure. They find new upper limits on the complexity of these divisions in different scenarios and create algorithms to compute them. Their work also helps improve how to quickly answer shortest path questions and find important points like the farthest distance or center inside the shape.
polygonal domainshortest path map (SPM)geodesic pathcombinatorial complexitytopological equivalencetwo-point shortest path queriesgeodesic diametergeodesic centercomputational geometryalgorithm
Authors
Haitao Wang
Abstract
Given a polygonal domain $P$ in the plane, the shortest path map with respect to a point $s$, denoted by $SPM(s)$, is the decomposition of $P$ into cells such that shortest paths from $s$ to all points $t$ in the same cell have the same vertex sequence. The shortest path map equivalence decomposition of $P$ is the decomposition of $P$ into cells so that $SPM(s)$ is topologically equivalent for all points $s$ in the same cell. In this paper, we prove new upper bounds on the combinatorial complexities of the $SPM$-equivalence decompositions under various settings, depending on whether $s$ and/or $t$ are restricted to the boundary of $P$. We also propose new algorithms to compute these decompositions. Further, our results lead to new solutions to several other problems, including answering two-point shortest path queries in $P$, and computing geodesic diameter and center of $P$.