2026-08-18T11:37:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17866 2024-03-06T11:00:34Z ddc:004 open_access

The Complexity of Geodesic Spanners de Berg, Sarita van Kreveld, Marc Staals, Frank spanner simple polygon polygonal domain geodesic distance complexity A geometric t-spanner for a set S of n point sites is an edge-weighted graph for which the (weighted) distance between any two sites p,q ∈ S is at most t times the original distance between p and q. We study geometric t-spanners for point sets in a constrained two-dimensional environment P. In such cases, the edges of the spanner may have non-constant complexity. Hence, we introduce a novel spanner property: the spanner complexity, that is, the total complexity of all edges in the spanner. Let S be a set of n point sites in a simple polygon P with m vertices. We present an algorithm to construct, for any constant ε > 0 and fixed integer k ≥ 1, a (2k + ε)-spanner with complexity O(mn^{1/k} + nlog² n) in O(nlog²n + mlog n + K) time, where K denotes the output complexity. When we consider sites in a polygonal domain P with holes, we can construct such a (2k+ε)-spanner of similar complexity in O(n² log m + nmlog m + K) time. Additionally, for any constant ε ∈ (0,1) and integer constant t ≥ 2, we show a lower bound for the complexity of any (t-ε)-spanner of Ω(mn^{1/(t-1)} + n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sarita de Berg and Marc van Kreveld and Frank Staals 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.16 urn:nbn:de:0030-drops-178669 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.16 eng https://creativecommons.org/licenses/by/4.0/legalcode