Personal tools
You are here: Home CG seminar 2020 Truly Optimal Euclidean Spanners
« December 2020 »
Log in

Forgot your password?

Truly Optimal Euclidean Spanners

Wednesday, December 25th, 2019, 16:10

Checkpoint 480


Truly Optimal Euclidean Spanners

Shay Solomon, TAU


A Euclidean (1 + ϵ)-spanner for a point set S in the d dimensional Euclidean space R^d is a subgraph of the complete Euclidean graph corresponding to S, which preserves all pairwise distances to within a factor of 1 + ϵ. 

Geometric spanners find many applications, from compact routing and distance oracles to robotics and machine learning.  In many of those applications, the spanners should be sparse either in the unweighted sense (small number of edges) or in the weighted sense (small weight).
Cornerstone results in the area from the 80s and 90s state that for any n-point set in R^d, there exists a (1+ϵ)-spanner with n O(ϵ^{−d+1}) edges and lightness (normalized weight) O(ϵ^{−2d}).
Surprisingly, the question of whether or not these dependencies on ϵ and d for small d can be improved has remained elusive, even for d=2.

In this talk I'll discuss this question and a few related questions, focusing mostly on the case d = 2.
The talk is self-contained and no prior knowledge is assumed.

Part of the talk is based on a joint work with Hung Le,
Document Actions