2026-09-20T16:43:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27253 2026-09-05T20:16:34Z ddc:004 open_access

Sparse Oriented Spanners in Metric Spaces Bhore, Sujoy Biniaz, Ahmad Buchin, Kevin De Carufel, Jean-Lou Kalb, Antonia Maheshwari, Anil Odak, Saeed Rehs, Carolin Smid, Michiel spanner oriented graph dilation doubling dimension orientation tournament well-separated pair decomposition Oriented spanners were presented at ESA'23 as an extension of the well-researched geometric spanners: Given a set P of points in a metric space and an oriented graph G, the oriented dilation of two points p,q ∈ P is the length of the shortest closed walk in G containing p and q divided by the minimum perimeter triangle of p and q. G is called a t-spanner, if the maximum dilation over all pairs of points in P is at most t. This paper presents the first constructions of sparse oriented spanners for metric spaces beyond the Euclidean space. Given an orientation of the complete graph (i.e. a tournament) with dilation t on n points that satisfies an additional short-cycle property, we show how to extract a (t+ε)-spanner with 𝒪(k) edges in 𝒪(kn²+T(n)) time, for any metric space admitting a well-separated pair decomposition with k pairs computable in T(n) time. We supplement this with an improved construction of tournaments for metric point sets, obtaining dilation 5/3. This improves the previous bound of 2 and approaches the lower bound of 1.5. Combined, for n points in a metric space with constant doubling dimension d, this yields a (5/3 + ε)-spanner with (1/ε)^{𝒪(d)}n edges computable in (1/ε)^𝒪(d) n³ time using 𝒪(n²) space. This improves the dilation over the (2+ε)-spanner for Euclidean point sets presented at SoCG’25 while applying to more general metric spaces. Moreover, we generalize the known (2+ε)-spanner to doubling spaces. In particular, an oriented (2+ε)-spanner with 𝒪(ε^{-d} n) edges can be constructed in (1/ε)^𝒪(d) n log n time using 𝒪(ε^{-d} n) space. Since the oriented dilation can be dominated by one pair of points, we also consider the oriented average dilation, which is the sum over the oriented dilation of all pairs of points divided by the number of pairs. While oriented (1+ε)-spanners do not exist for every point set, we present an algorithm that computes a spanner with average dilation 1+ε for point sets in a metric space of constant doubling dimension d: More concretely, our algorithm computes an oriented spanner with average dilation at most 1 + 𝒪(1/s) + s^𝒪(d)/n with s^𝒪(d) n edges in s^𝒪(d) n log n time using s^𝒪(d) n space, where s is any sufficiently large number that may depend on n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sujoy Bhore and Ahmad Biniaz and Kevin Buchin and Jean-Lou De Carufel and Antonia Kalb and Anil Maheshwari and Saeed Odak and Carolin Rehs and Michiel Smid 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.117 urn:nbn:de:0030-drops-272532 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.117 eng https://creativecommons.org/licenses/by/4.0/legalcode