0

I'm trying to solve the following variation of the Hellys theorem problem:

Let $B = {B(o_i,r):i = 1,...,n}$ a set of balls with radius r with center at $o_i\in\mathbb{R}^2$. Compute the minimal radius r such that: $\bigcap_{i=0}^n B(o_i,r)\neq\varnothing$

image example of the problem

  • Where should I start to solve this question? (There is no prior knowledge about $o_i$ which obviously has an effect on the answer, this fact makes it hard for me to approach this problem)
  • Which parametric equations represent this problem?
  • Is there any way to write a Matlab/Python code to visualize/validate this problem?

Here is my intuition: Since all the balls have the same $r$ value the minimum $r$ which guarantees the given condition is the maximum distance between two balls in the group divided by two (since the distance is a diameter). Am I right?

AvivSham
  • 61
  • 1
    Your intuition is not correct, consider the three vertices of an equilateral triangle. What you are looking for is https://en.wikipedia.org/wiki/Smallest-circle_problem – Michal Adamaszek Nov 20 '19 at 09:56
  • I think you missed the point. The question here is what is the smallest radius which will lead to the mutual intersection between all the balls in the group and not the smallest circle which will contain them all. – AvivSham Nov 20 '19 at 10:03
  • But it is the same question. The smallest radius when the balls intersect determines the center and radius of the smallest enclosing circle and vice versa. – Michal Adamaszek Nov 20 '19 at 10:11
  • No. Please check the edited question with the example photo. – AvivSham Nov 20 '19 at 10:21

1 Answers1

1

We have $$y\in \bigcap_i B(O_i,r)$$ if and only if $$O_i\in B(y,r)\quad \mbox{for all } i.$$ Therefore your problem is equivalent to the problem of finding the smallest disk containing all of $O_i$.The link https://en.wikipedia.org/wiki/Smallest-circle_problem contains some algorithms. You can also write it as a minimization problem $$\min_y \max_i\{\|y-O_i\|\}$$ and throw any available quadratic (QP) or second-order cone (SOCP) solver at it. Or see https://www.nayuki.io/page/smallest-enclosing-circle for a nice example with some code.

Michal Adamaszek
  • 4,018