3
$\begingroup$

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.

$\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$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.