A note on the inflating enclosing ball problem

Résumé

Our goal in this paper is, given a connected set of balls, to select and inflate one ball to cover the whole set with the minimal radius. More formally, we are given an abstract metric space and a path-connected set of balls with given centres $c_1,c_2,\dots, c_n$ and radii $r_1, r_2,\dots, r_n$. We want to choose one of the centres and create a ball of radius $R$ around it to cover the whole set of balls with minimal $R$. By using arguments from graph theory, we show that $R <= r_a+∑_jr_j$, where $r_a$ is the mean of the two biggest radii among the $r_i$. This bound is tight. Finally, we show that in the usual complexity models, computing this centre requires $Θ(n^2)$ operations.

Publication
Proceedings of the 5th Bordeaux Graph Workshop, BGW 2019, Bordeaux, France, October 28-31, 2019