Geometry Seminar

Oriented Spanners in Metric Spaces

Speaker: Michiel Smid, Carlton U

Location: Online

Date: Tuesday, September 15, 2026, 2 p.m.

Synopsis:

A \(t\)-spanner of a finite metric space \((P,\|\cdot\|)\) is an undirected graph \(G\) with vertex set \(P\) such that for every pair \(p,q\) of points in \(P\), their shortest-path distance in \(G\) is at most \(t \cdot |pq|\). It follows from the triangle inequality that \(t\) cannot be less than one. If \(P\) is a set of \(n\) points in a Euclidean space of constant dimension, then a \((1+\varepsilon)\)-spanner with \(O(n)\) edges exists for any constant \(\varepsilon>0\). A standard proof of this result uses the well-separated pair decomposition (WSPD) of Callahan and Kosaraju from 1995.

In 2023, the notion of oriented spanners was introduced.

  • For every pair \(p,q\) of points in \(P\), let \(\Delta(p,q)\) denote the perimeter of a shortest triangle in \(P\) through \(p\) and \(q\).
  • Let \(G\) be an oriented graph with vertex set \(P\), i.e., if \((u,v)\) is an edge in \(G,\) then \((v,u)\) is not an edge in \(G\).
  • Let \(C_G(p,q)\) denote the length of a shortest oriented cycle in \(G\) through \(p\) and \(q\).
  • The graph \(G\) is called an oriented \(t\)-spanner, if for all points \(p\) and \(q\) in \(P,\) the oriented dilation \(C_G(p,q) / \Delta(p,q)\) is at most \(t\).

Again, the triangle inequality implies that \(t\) cannot be less than one. In fact, there are metric spaces for which  \(t\) cannot be less than 3/2. There are also point sets in the Euclidean plane for which \(t\) cannot be less than \(2 \sqrt{3} - 2 \approx 1.464\).

In this talk, I will give an introduction to the WSPD and oriented spanners. I will show that for \(n\) points in a Euclidean space of constant dimension, the WSPD can be used to construct an oriented graph \(G\) with \(O(n)\) edges and average oriented dilation at most \(1+\varepsilon\), for any constant \(\varepsilon>0.\)

See here for a PDF version of the talk abstract.

Notes:

Only on Zoom.  Please contact Boris Aronov to be put on the email announcement list and obtain Zoom details.