patternMinor
Checking for intersection of $d$-dimensional spheres
Viewed 0 times
spherescheckingforintersectiondimensional
Problem
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.
In other words, check whether there is a point $p$ that is contained in all $n$ balls.
Solution
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.
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.
Context
StackExchange Computer Science Q#83473, answer score: 4
Revisions (0)
No revisions yet.