0

I am provided with the radii and coordinates of the centers of $n$ circles. I want know whether all circle have common area. I don't need to calculate the area.

First, I think if all circles intersect each other, they have common area.But it's wrong.

After searching for a period of time, I found a method is iterative and calculate the area at the same time.So is there any other way to find whether $n$ circles are overlapping over a common area quickly?

YCChiang
  • 1
  • I wonder what is your iterative method. – Arctic Char Aug 30 '21 at 09:08
  • 1
    This similar question: common overlap of n circles has several answers with proposed algorithms. Exert a critical mind, though: there is no proof provided of the correctness of the algorithms, and I think some of them are not correct (in the sense that they would return the wrong result on some test cases) – Stef Aug 30 '21 at 09:19
  • 3
    https://math.stackexchange.com/questions/605826/check-whether-n-disks-intersect – Asinomás Aug 30 '21 at 09:46
  • I would just add - for each pair of centers, the distance between them needs to be smaller than the sum of radii. – Moti Aug 30 '21 at 16:25
  • @Moti : you give a necessary condition, not a sufficient one. – Jean Marie Aug 30 '21 at 19:18
  • @Jean It needs to be true for every pair - you may improve it with some additional tests. I did not see this basic condition in the reference - but I may missed it. – Moti Aug 31 '21 at 18:23
  • @Moti imagine you have 3 circles with radius 0.51 centered in the vertices of an equilateral triangle with sidelength 1 : each pair of circles has an overlap zone but the 3 circles don't have a common overlap zone... – Jean Marie Aug 31 '21 at 18:51
  • @Jean You are right! This is a necessary condition. – Moti Aug 31 '21 at 18:53

0 Answers0