Find point covered by all given circles

Question

Given is $n$ circles ($n \le 1000$) circles where the $x$- and $y$-coordinates of their centers, and their radii, are all at most $10^6$.

The problem is to find a point in $\mathbb{R}^2$ covered by all circles, or to determine that there is no such point.

I think (and edited your problem to say) specifically that you are looking for a point, rather than, say, a description of the set of all such points. Presumably the problem is to find an efficient (how efficient?) algorithm to do this; either such a point exists or it doesn't, so, without giving some precise meaning to 'determine', the problem seems hard to understand. — LSpice, Commented Dec 27, 2020 at 0:29
Also, since you have given a fixed number of circles, it's hard to know how to measure the efficiency of the algorithm, so I guess 1000 was just for fun. The bound on the sizes of $x$- and $y$-coordinates and of radii seems superfluous, since the problem can be scaled to make all of those as small as desired. — LSpice, Commented Dec 27, 2020 at 0:31

Joseph O'Rourke · Accepted Answer · 2020-12-26 22:51:29Z

4

You might use Helly's Theorem: $n \ge 3$ convex sets in the plane have a common intersection if and only if every three of the sets intersects.

There are faster algorithms:

Aurenhammer, Franz. "Improved algorithms for discs and balls using power diagrams." Journal of Algorithms 9, no. 2 (1988): 151-161. DOI.

Later edit. I found this nice figure in answer to an MSE question, the intersection of n disks/circles:

Disks

answered Dec 26, 2020 at 13:48

Joseph O'Rourke

151k36 gold badges358 silver badges958 bronze badges

$\begingroup$ I can determine if there is an intersection using Helly's theorem, yes, but I can't find any point inside the intersection, can I? $\endgroup$
– ValeraGrinenko
Commented Dec 26, 2020 at 14:10
$\begingroup$ Ok, you helped, ty <3 $\endgroup$
– ValeraGrinenko
Commented Dec 26, 2020 at 14:24

Add a comment |

1 Answer 1