Longest chord in the intersection n disks (circle areas)

Question

Given n disks that intersect, there is a shape in the space where they intersect. Given that, what is the longest chord, more generally longest line, that can be drawn in this space? For n=1, this is the diameter For n=2, the result can be found on wolfram

What is the result for n>2? Bounds, estimates, and closed form equations will get you the bounty. Algorithms that don't guess can also get you the bounty. And I've already read Longest chord inside the intersection area of three circles.

I'm going to use this result to find appropriate diameters for covers that are the union of an arbitrary number of circles. Specifically this can be used to estimate the Hausdorff measures and dimensions of fractals. So if you have a suggestion for doing that, I'd appreciate it. If you know exactly what I'm talking about at this point, you could suggest I use a different shape, such as a square or oval, since it would give an easier equation.

Answer 1

With 2 circles there are three relevant configurations:

• no intersection/touching (max length = 0 and we are done)
• intersection in 2 points
• one circle completely inside another (in which case we just ignore the outer circle)

Adding another, N-th circle can have each of the 3 configurations with respect to all the other circles, for a total of $3^{N(N-1)/2}$ configurations with up to $N(N+1)$ intersection points. Simply determining which case you have at hand is bothersome and any analytical plug&chug formula where you just use all the center positions and radii would be ridiculously long and inefficient.

Lets use your example (positions (2,2);(-4,-4);(1,3);(3,2);(-1,-1) and the diameter radius of each circle is 5 (with a diameter of 5 the solution is trivial since there is no overlap)) and find the solution manually.

• we want to shrink the upper bound as fast as possible, so we compute all $\frac{N(N+1)}{2}$ distances between centers and pick the two circles furthest apart
• that gives us two intersection points $p_1$ and $p_2$ (at around (1,-3) and (-2,0.5)) and a lens-shaped area $A$, now compute the distance between those points and the centers of all the unused circles, find the highest distance $d_{max}$ (here, the distace between $p_2 \approx (1,-3)$ and the center at (1,3)
• if $d_{max}$ < 5 then $A$ lies entirely within the other circles without being intersected, therefore we are done. If not, which is the case here, we find the intersection of that new circle (the one around (1,3)) with the previous ones (it intersects the circles in 4 points, but we are only interested in those that lie on the perimeter of A)
• repeat the last two steps, finding the circles which are close enough to the perimeter of $A$, until the area isn't shrinking anymore. The longest line is the greatest of the distances between all the intersection points on the perimeter of $A$

If the radii are all different then it gets more complicated but the general idea is the same, and here is a sketch that will hopefully clarify what i am talking about

Answer 2

Clearly, the lower bound is 0, which is achievable if all circles are disjoint.

The upper bound is the smallest diameter (say circle $C$ has the smallest diameter), which is also achievable by placing all circles through a pair of antipodals of $C$.

Answer 3

The ellipsoid of maximum area that is wholly contained within the intersection of circles (indeed, ellipsoids) can be computed with convex optimization. The details of the mathematics can be found in Section 8.4.2 of Convex Optimization by Boyd & Vandenberghe. Below I summarize the relevant portion of the material, simplified by the fact that your ellipsoids are all circles.

The target ellipsoid $\mathcal{E}$ is parameterized as follows: $$\mathcal{E}=\{Bu+d\,|\,\|u\|_2\leq 1\}$$ where $B$ is a symmetric positive definite matrix and $d$ is a vector. Each circle $\mathcal{C}_i$ is described by its center $v_i$ and radius $r_i$. The maximum volume ellipsoid is the solution to the semidefinite program \begin{array}{ll} \text{maximize}_{\lambda,B,d} & \log\det B \\ \text{subject to} & \begin{bmatrix} r_i^2-\lambda_i & 0 & d^T-v_i^T \\ 0 & \lambda_i I & B \\ d - v_i & B & I \end{bmatrix} \succeq 0, ~ i=1,2,\dots, m \end{array} The optimization variables are $B$, $d$, and one $\lambda_i\geq 0$ for each circle.

It's quite possible this model can be simplified further; constraining the ellipsoids to be circles has introduced a lot of structure. I will consider this further and edit if necessary.

Once you have this ellipsoid, you could extract its major axis and use that as an approximate chord. You can improve the approximation by computing scaling it until it intersects one or more of the circles.

Answer 4

This problem is more difficult than just identifying the intersection region, for which the accepted answer gives an algorithm. The issue with that answer is that the final line of the algorithm is incorrect ("the longest line is the greatest of the distances between all the intersection points on the perimeter of A"). In fact, the longest line may be between an intersection point and a point in the interior of an arc, or between two interior points.

The image below is an example of the first case: the diameter of the intersection region is equal to the diameter of the yellow circle, but no two of the three intersection points are that far apart. To see an example of the second case, push the red circle slightly to the left; again, the diameter of intersection region will be equal to the yellow circle's diameter, but no two of the four intersection points will be that far apart.