9
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Since you're talking about intersect area, I take it you mean discs, not circles. The disc includes the interior of the circle, whereas circle only refers to the perimeter. Perhaps it would be good to clearify? $\endgroup$ – Einar Rødland Dec 13 '13 at 20:01
  • $\begingroup$ I changed my description from circles to disks $\endgroup$ – reindeer Dec 13 '13 at 20:09
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I did not know that there is a difference between circles and disks until I read about it after your remark. I think I deal with disks here (the area inside and the border count as stuff to intersect with) $\endgroup$ – reindeer Dec 13 '13 at 20:02
  • $\begingroup$ I have no idea what a finite field extension is or how it works, so b) is no direct option right now. My $n$ is in the order of $10^3$ . Is implementation of c) just three for loops (i,j,k) nested which check $D_i \cap D_j \cap D_k = \emptyset $? $\endgroup$ – reindeer Dec 13 '13 at 22:04
  • $\begingroup$ Yes, (c) is just like that. For (b), ignore the fancy words. Just represent numbers like $a + b \sqrt{c}$ as triplets $(a, b, c)$ of rational numbers, and implement all arithmetic operations and comparison ($\leq$) on your own. This way you should be able to represent precisely positions of all points where circles intersect. $\endgroup$ – Dan Shved Dec 14 '13 at 6:12
  • $\begingroup$ P4 of this article describes an O(n ln n) algorithm using power diagrams, which can be computed via CGAL. $\endgroup$ – obsolesced Oct 31 '16 at 4:47
  • $\begingroup$ Thanks for the idea of using an extension of rationals to solve floating point problems. Would you know of any available code for such an extension? $\endgroup$ – obsolesced Oct 31 '16 at 5:07
0
$\begingroup$

This can be done quickly enough. To know the circles, one must have their centers and radii. Then calculate using this to see if any of the circles intersect. Assuming that the circles are distinct, if any pair of them intersect, they will do so at most twice. Take these two points and have the computer check to see if they satisfy the equations for the other circles.

$\endgroup$
0
$\begingroup$

First, sort the disks by size, and discard any disk that entirely contains another. If only a single disk remains, return $\mathtt{true}$. Iterate over all remaining pairs of disks. For each pair:

  • If they are disjoint, return $\mathtt{false}$.
  • Otherwise, their boundaries intersect at exactly one or two points. Check whether the intersection point(s) are contained in all the remaining disks. If they are, return $\mathtt{true}$; otherwise continue.

Finally, if all pairs have been checked, return $\mathtt{false}$.

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