I struggle with the following problem:
Given $N$ disks $D_i = (x_i, y_i,r_i)$, calculate whether they ALL intersect.
$D_1 \cap D_2 \cap \dots \cap D_N = \emptyset $ ?
I do not care about the intersection area, just want to know whether they do or not.
I know how to check whether two disks intersect.
I read
the intersection of n disks/circles
But their algorithm seems to be not 100% accurate, since floating point arithmetics and focused on the calculation of the resulting area.
I thought about representing disks as a set, like:
The set of all points equidistant from the center,
but that does not help me too much. My idea was, given a point $p$,
all $N$ disks intersect $ \iff \exists \ p: p \in D_1 \wedge p \in D_2 \wedge \dots \wedge p \in D_N $,
but the only way to implement that into code that comes to my mind is to use Monte Carlo, and that is (maybe) slow and not accurate either.
Does somebody know a fast and hopefully easy solution?
Edit: Changed from circles to disks, after it was pointed out that I mean disks.
Best Answer
It's not very clear whether the problem is about disks or about circles. Here are some suggestions for both cases.
If it is about disks, then you can use Helly`s theorem. It says that $n \geq 3$ disks on a plane intersect if and only if every $3$ disks among them intersect. And for $3$ disks I believe it should be quite easy to produce an exact solution (i.e. one that is 100% precise if all centers and radii are given as rational numbers).
This is not the fastest approach, but I believe it can be implemented precisely without any serious complications, and without the use of floating point operations.
If the problem is about circles and not about disks, then you can also make the solution precise, but you will have to manipulate elements of some quadratic extension of $\mathbb{Q}$, i.e. you'll have to do symbolic manipulations with expressions like $a + b\sqrt{c}$.
UPDATE: since you're talking about code, I should add this bit: it all depends on the exact circumstances and the exact quality/speed requirements.
a) If this is a programming contest, then I wouldn't use Helly's theorem. Instead, I would do something like the following, which takes time $O(n^2 \ln n)$.
If all the disks have a common point, then they also have a common point that lies on the border of one of the disks. So, for every disk $D$, I would check whether or not there is a point on its border (which is a circle $S$) that belongs to all other disks.
To do that, I would find the intersections of this border $S$ with every other disc. Each such intersection is an arc of $S$, a point on $S$, an empty set, or the whole $S$. And then I'd determine whether or not these arcs have a common point, which can be done in time $O(n \ln n)$ by sorting the endpoints of the arcs (say) clockwise. I would do it all using floating-point arithmetic with an appropriate epsilon value. In fact, this is what I did a couple of times in actual competitions back in the day.
b) If the code should be industrial and absolutely precise, then it should be possible (in principle) to do the same as above, but instead of floating point arithmetic do precise arithmetic in an appropriate finite field extension of $\mathbb{Q}$. But I've never tried to implement this myself. Could be kind of difficult.
c) If execution time is not as important but you still need absolute precision, then I would go with Helly's theorem. It could simplify the code thus making it much more robust, but execution time will grow to $n^3$.