Optimal spanners in Euclidean spaces

Abstract

For a set S of n points in a metric space (X,d) and a parameter t>1, a t-spanner is a weighted graph G=(S,E) such that the shortest path distance in G approximates the pairwise distances in the metric space up to a factor of at most t. The parameter t is called the stretch factor of G. This talk is concerned with the d-dimensional Euclidean space in the regime where the stretch t is close to 1. Recent research uncovered tight trade-offs for two important quality measures for t-spanners: the sparsity |E(G)|/n and the lightness w(G)/w(MST(S)). This talk will present a new algorithm that constructs a t-spanner for a given set of n points in Euclidean d-space, by sparsifying classical Yao-graphs, and attains a worst-case optimal bound on the weight of the spanner.

In the online model, a sequence of n points arrive one-by-one, and we need to maintain a t-spanner for the current point set at all times. By combining sparse Yao-graphs with hierarchical clustering, we obtain an online algorithm that maintains a light spanner and achieves logarithmic competitive ratio compared to the offline optimum.

Bio:

Csaba D. Toth is a professor in mathematics at California State University Northridge, in Los Angeles, CA, and holds an affiliate appointment in computer science at Tufts University, in Medford, MA. He works on problems at the intersection of combinatorics, metric geometry, and low-dimensional topology. He is an author of more than hundred research papers in collaboration with 170 coauthors. Csaba is a Coeditor-in-Chief of Discrete & Computational Geometry, and serves on the editorial board of three open access journals.

Please join meeting in Cummings 270 or via Zoom.

Join Zoom Meeting: https://tufts.zoom.us/j/96038251227

Meeting ID: 960 3825 1227

Passcode: see colloquium email

Dial by your location: +1 646 558 8656 US (New York)

Meeting ID: 960 3825 1227

Passcode: see colloquium email