2026-09-18T02:43:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24264 2026-09-05T18:40:14Z ddc:004 open_access

Spanner for the 0/1/∞ Weighted Region Problem Gudmundsson, Joachim Huang, Zijin van Renssen, André Wong, Sampson weighted region problem approximate shortest path spanner We consider the problem of computing an approximate weighted shortest path in a weighted planar subdivision, with weights assigned from the set {0, 1, ∞}. The subdivision includes zero-cost regions (0-regions) with weight 0 and obstacles with weight ∞, all embedded in a plane with weight 1. In a polygonal domain, where the 0-regions and obstacles are non-overlapping polygons (not necessarily convex) with in total N vertices, we present an algorithm that computes a (1 + ε)-approximate spanner of the input vertices in expected Õ(N/ε³) time, for 0 < ε < 1. Using our spanner, we can compute a (1 + ε)-approximate weighted shortest path between any two points (not necessarily vertices) in Õ(N/ε³) time. Furthermore, we prove that our results more generally apply to non-polygonal convex regions. Using this generalisation, one can approximate the weak partial Fréchet similarity [Buchin et al., 2009] between two polygonal curves in expected Õ(n²/ε²) time, where n is the total number of vertices of the input curves. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joachim Gudmundsson and Zijin Huang and André van Renssen and Sampson Wong 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.33 urn:nbn:de:0030-drops-242644 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.33 eng https://creativecommons.org/licenses/by/4.0/legalcode