Personal tools
You are here: Home CG seminar 2020 Truly Optimal Euclidean Spanners
« December 2020 »
December
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

Truly Optimal Euclidean Spanners

Wednesday, December 25th, 2019, 16:10

Checkpoint 480

underline

Truly Optimal Euclidean Spanners

Shay Solomon, TAU

Abstract:

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,  https://arxiv.org/abs/1904.12042
Document Actions