2026-09-23T08:50:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27296 2026-09-05T20:18:20Z ddc:004 open_access

Shortest Path Map Equivalence Decompositions and Applications Wang, Haitao shortest paths shortest path maps SPM-equivalent decompositions two-point shortest path queries geodesic diameter geodesic center polygononal domains Given a polygonal domain 𝒫 in the plane, the shortest path map with respect to a point s, denoted by SPM(s), is the decomposition of 𝒫 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 𝒫 is the decomposition of 𝒫 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 be the boundary of 𝒫. 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 𝒫, and computing geodesic diameter and center of 𝒫. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.160 urn:nbn:de:0030-drops-272966 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.160 eng https://creativecommons.org/licenses/by/4.0/legalcode