Is there a simple algorithm to check whether $n$ different balls (of the same radius) in $\mathbb{R}^d$ intersect? That is, coordinates of their centers $x_i$ are given, radius $R$ is given and we need to determine if there exists a point $p$ such that $$\| p - x_i \| \leq R \quad \forall i.$$ In other words, check whether there is a point $p$ that is contained in all $n$ balls.
3
$\begingroup$
$\endgroup$
-
1$\begingroup$ related? cs.stackexchange.com/questions/23942/… $\endgroup$ – guest Nov 5 '17 at 18:20
-
$\begingroup$ Right now I am using $\| \cdot \|_{\infty}$ for simplicity, in this case it is just a collection of $1$d checks. For the euclidiean norm I was thinking about writing an optimization problem and checking its feasibility using some optimizer. $\endgroup$ – Mathemage Nov 5 '17 at 19:51
2
$\begingroup$
$\endgroup$
This is an instance of the smallest enclosing ball problem.
An equivalent statement of your problem is: Given points $x_1,\dots,x_n$, we want to determine whether there exists a point $p$ such that every point $x_i$ is at distance at most $R$ from $p$, i.e., we want to find a sphere of radius $R$ that encloses all of the points $x_1,\dots,x_n$.
So, find the smallest enclosing ball that contains all of $x_1,\dots,x_n$; then check whether the radius of that ball is at most $R$ or not. The smallest enclosing ball problem is well-studied and you can find references and algorithms in the Wikipedia page I linked to.
