# Truly Optimal Euclidean Spanners

### Wednesday, December 25th, 2019, 16:10

### Checkpoint 480

### 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

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